Submission #2690872
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]--; if(m>c[i]) m=c[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); } } 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 | 1545 Byte |
Status | WA |
Exec Time | 82 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 | 2 ms | 4480 KB |
sample_02.txt | AC | 3 ms | 3968 KB |
subtask_1_01.txt | AC | 3 ms | 4736 KB |
subtask_1_02.txt | WA | 61 ms | 9208 KB |
subtask_1_03.txt | AC | 32 ms | 6784 KB |
subtask_1_04.txt | WA | 63 ms | 9592 KB |
subtask_1_05.txt | AC | 34 ms | 7424 KB |
subtask_1_06.txt | WA | 27 ms | 6780 KB |
subtask_1_07.txt | WA | 28 ms | 6524 KB |
subtask_1_08.txt | AC | 33 ms | 6648 KB |
subtask_1_09.txt | WA | 22 ms | 5888 KB |
subtask_1_10.txt | WA | 9 ms | 5120 KB |
subtask_1_11.txt | AC | 18 ms | 6176 KB |
subtask_1_12.txt | WA | 68 ms | 9464 KB |
subtask_1_13.txt | AC | 67 ms | 9720 KB |
subtask_1_14.txt | WA | 73 ms | 9720 KB |
subtask_1_15.txt | AC | 67 ms | 9464 KB |
subtask_1_16.txt | WA | 73 ms | 9720 KB |
subtask_1_17.txt | AC | 69 ms | 9720 KB |
subtask_1_18.txt | WA | 69 ms | 9460 KB |
subtask_1_19.txt | AC | 68 ms | 9464 KB |
subtask_1_20.txt | AC | 71 ms | 9464 KB |
subtask_1_21.txt | AC | 65 ms | 9720 KB |
subtask_1_22.txt | AC | 68 ms | 9460 KB |
subtask_1_23.txt | AC | 63 ms | 9592 KB |
subtask_1_24.txt | AC | 82 ms | 9208 KB |
subtask_1_25.txt | WA | 79 ms | 9592 KB |
subtask_1_26.txt | WA | 75 ms | 9720 KB |
subtask_1_27.txt | AC | 65 ms | 8948 KB |
subtask_1_28.txt | WA | 66 ms | 9720 KB |
subtask_1_29.txt | AC | 75 ms | 9208 KB |
subtask_1_30.txt | AC | 79 ms | 9208 KB |
subtask_1_31.txt | AC | 71 ms | 10232 KB |
subtask_1_32.txt | WA | 60 ms | 9972 KB |
subtask_1_33.txt | AC | 36 ms | 9332 KB |
subtask_1_34.txt | AC | 46 ms | 10740 KB |