Submission #2667660
Source Code Expand
#include<bits/stdc++.h> using namespace std; typedef pair<int,int>ii; typedef pair<int,ii>iii; typedef vector<int>vi; vector<vi>adjlist; vector<iii>edge; const int N=1e5+5; long long ans[N],lazy[N]; int pa[N],sz[N]; void unionset(int x,int y,int w) { x=pa[x]; y=pa[y]; if(sz[x]<sz[y]){ lazy[y]+=sz[x]*w; for(int i=0;i<adjlist[x].size();++i){ int v=adjlist[x][i]; pa[v]=y; adjlist[y].push_back(v); ans[v]+=lazy[x]; ans[v]+=sz[y]*w; ans[v]-=lazy[y]; } sz[y]+=sz[x]; } else{ lazy[x]+=sz[y]*w; for(int i=0;i<adjlist[y].size();++i){ int v=adjlist[y][i]; pa[v]=x; adjlist[x].push_back(v); ans[v]+=lazy[y]; ans[v]+=sz[x]*w; ans[v]-=lazy[x]; } sz[x]+=sz[y]; } } int main() { int n; scanf("%d",&n); adjlist.assign(n+1,vi()); for(int i=1;i<=n;++i){ adjlist[i].push_back(i); pa[i]=i; sz[i]=1; } for(int i=1;i<n;++i){ int u,v,w; scanf("%d%d%d",&u,&v,&w); edge.push_back(iii(w,ii(u,v))); } sort(edge.begin(),edge.end()); reverse(edge.begin(),edge.end()); for(int i=0;i<edge.size();++i){ unionset(edge[i].second.first,edge[i].second.second,edge[i].first); } int root=0; for(int i=1;i<=n;++i)if(pa[i]==i)root=i; for(int i=0;i<adjlist[root].size();i++)ans[adjlist[root][i]]+=lazy[root]; for(int i=1;i<=n;++i)printf("%lld\n",ans[i]); }
Submission Info
Submission Time | |
---|---|
Task | E - Black Cats Deployment |
User | vjudge4 |
Language | Bash (GNU bash v4.3.11) |
Score | 0 |
Code Size | 1567 Byte |
Status | RE |
Exec Time | 6 ms |
Memory | 632 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 200 | 0 / 400 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt |
Subtask2 | 00_example_02.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt |
All | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s2_08.txt, s2_09.txt, s2_10.txt, s2_11.txt, s2_12.txt, s2_13.txt, s2_14.txt, s3_15.txt, s3_16.txt, s3_17.txt, s3_18.txt, s3_19.txt, s3_20.txt, s3_21.txt, s3_22.txt, s3_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | RE | 6 ms | 608 KB |
00_example_02.txt | RE | 6 ms | 608 KB |
00_example_03.txt | RE | 6 ms | 632 KB |
s1_01.txt | RE | 6 ms | 608 KB |
s1_02.txt | RE | 6 ms | 608 KB |
s1_03.txt | RE | 6 ms | 608 KB |
s1_04.txt | RE | 6 ms | 608 KB |
s1_05.txt | RE | 6 ms | 608 KB |
s1_06.txt | RE | 6 ms | 608 KB |
s1_07.txt | RE | 6 ms | 608 KB |
s2_08.txt | RE | 6 ms | 608 KB |
s2_09.txt | RE | 6 ms | 632 KB |
s2_10.txt | RE | 6 ms | 632 KB |
s2_11.txt | RE | 6 ms | 608 KB |
s2_12.txt | RE | 6 ms | 604 KB |
s2_13.txt | RE | 6 ms | 608 KB |
s2_14.txt | RE | 6 ms | 608 KB |
s3_15.txt | RE | 6 ms | 612 KB |
s3_16.txt | RE | 6 ms | 632 KB |
s3_17.txt | RE | 6 ms | 632 KB |
s3_18.txt | RE | 6 ms | 608 KB |
s3_19.txt | RE | 6 ms | 608 KB |
s3_20.txt | RE | 6 ms | 628 KB |
s3_21.txt | RE | 6 ms | 608 KB |
s3_22.txt | RE | 6 ms | 608 KB |
s3_23.txt | RE | 6 ms | 608 KB |
s3_24.txt | RE | 6 ms | 604 KB |
s3_25.txt | RE | 6 ms | 632 KB |
s3_26.txt | RE | 6 ms | 608 KB |
s3_27.txt | RE | 6 ms | 608 KB |
s3_28.txt | RE | 6 ms | 612 KB |
s3_29.txt | RE | 6 ms | 604 KB |