Submission #2691592
Source Code Expand
#include <cstdio> #include <cstring> #include <iostream> #include <string> #include <cmath> #include <bitset> #include <vector> #include <map> #include <set> #include <queue> #include <deque> #include <algorithm> #define INF 1000000000000000LL using namespace std; typedef long long int ll; typedef pair<int, int> P; int main() { int n; scanf("%d", &n); int a[100000], b[100000]; ll c[100000]; ll m=INF; vector<P> v[100000]; for(int i=0; i<n-1; i++){ scanf("%d %d %lld", &a[i], &b[i], &c[i]); a[i]--; b[i]--; v[a[i]].push_back(P(b[i], i)); v[b[i]].push_back(P(a[i], i)); } int d[100000]; vector<P> dist; fill(d, d+n, -1); d[0]=0; queue<int> que; que.push(0); while(!que.empty()){ int x=que.front(); que.pop(); for(int i=0; i<v[x].size(); i++){ int y=v[x][i].first; if(d[y]<0){ d[y]=d[x]+1; que.push(y); } } } for(int i=0; i<n; i++){ dist.push_back(P(d[i], i)); } sort(dist.begin(), dist.end(), greater<P>()); int count[100000]={}; for(int i=0; i<n; i++){ int x=dist[i].second; for(int j=0; j<v[x].size(); j++){ int y=v[x][j].first; if(d[y]<d[x]) continue; count[x]+=(count[y]+1); } } for(int i=0; i<n; i++){ bool e1=0; for(int j=0; j<v[i].size(); j++){ int y=v[i][j].first; if(d[i]>d[y] && n-count[y]>n/2){ e1=1; break; }else if(d[i]<d[y] && count[y]+1>n/2){ e1=1; break; } } if(e1==0){ for(int j=0; j<v[i].size(); j++){ if(m>c[v[i][j].second]) m=c[v[i][j].second]; } break; } } ll ans=0; bool e=0; for(int i=0; i<n-1; i++){ int x=a[i], y=b[i]; int c1=min(count[x], count[y])+1, c2=n-c1; if(c1==c2){ e=1; ans+=((ll)(2*c1-1)*c[i]); }else{ ans+=(2*(ll)(min(c1, c2))*c[i]); } } if(e==0){ ans-=m; } printf("%lld\n", ans); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Tree and Hamilton Path |
User | chocorusk |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1890 Byte |
Status | WA |
Exec Time | 66 ms |
Memory | 10740 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:22:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &n); ^ ./Main.cpp:28:43: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d %lld", &a[i], &b[i], &c[i]); ^
Judge Result
Set Name | Sample | All | ||||||
---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 1100 | ||||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
All | sample_01.txt, sample_02.txt, sample_01.txt, sample_02.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 3 ms | 4224 KB |
sample_02.txt | AC | 3 ms | 3712 KB |
subtask_1_01.txt | AC | 3 ms | 3968 KB |
subtask_1_02.txt | WA | 57 ms | 8948 KB |
subtask_1_03.txt | AC | 30 ms | 6528 KB |
subtask_1_04.txt | WA | 59 ms | 9592 KB |
subtask_1_05.txt | AC | 33 ms | 7168 KB |
subtask_1_06.txt | WA | 27 ms | 7036 KB |
subtask_1_07.txt | WA | 27 ms | 6264 KB |
subtask_1_08.txt | AC | 31 ms | 7164 KB |
subtask_1_09.txt | WA | 21 ms | 6144 KB |
subtask_1_10.txt | WA | 9 ms | 4736 KB |
subtask_1_11.txt | WA | 18 ms | 5792 KB |
subtask_1_12.txt | WA | 63 ms | 9460 KB |
subtask_1_13.txt | AC | 62 ms | 9720 KB |
subtask_1_14.txt | WA | 64 ms | 9464 KB |
subtask_1_15.txt | AC | 66 ms | 9460 KB |
subtask_1_16.txt | WA | 65 ms | 9720 KB |
subtask_1_17.txt | AC | 63 ms | 9720 KB |
subtask_1_18.txt | WA | 64 ms | 9592 KB |
subtask_1_19.txt | AC | 63 ms | 9720 KB |
subtask_1_20.txt | AC | 64 ms | 9464 KB |
subtask_1_21.txt | AC | 63 ms | 9720 KB |
subtask_1_22.txt | AC | 65 ms | 9720 KB |
subtask_1_23.txt | AC | 60 ms | 9592 KB |
subtask_1_24.txt | AC | 60 ms | 9208 KB |
subtask_1_25.txt | WA | 64 ms | 9720 KB |
subtask_1_26.txt | WA | 63 ms | 9720 KB |
subtask_1_27.txt | AC | 59 ms | 9208 KB |
subtask_1_28.txt | WA | 64 ms | 9592 KB |
subtask_1_29.txt | AC | 60 ms | 9208 KB |
subtask_1_30.txt | AC | 61 ms | 8948 KB |
subtask_1_31.txt | WA | 65 ms | 10232 KB |
subtask_1_32.txt | WA | 58 ms | 9972 KB |
subtask_1_33.txt | WA | 34 ms | 9076 KB |
subtask_1_34.txt | WA | 45 ms | 10740 KB |