Submission #2666738
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
struct edge{
int u,v;
long long w;
edge(int a,int b,long long c):u(a),v(b),w(c){}
};
long long lazy[N],res[N];
int n,p[N];
vector<vector<int> > sets;
vector<edge> E;
bool cmp(edge &a,edge &b){
return a.w<b.w;
}
void dsu(int i,int j,long long w){
for(int k=0;k<sets[i].size();k++){
res[sets[i][k]]+=lazy[i]-lazy[j]+w*sets[j].size();
p[sets[i][k]]=j;
}
for(int k=0;k<sets[i].size();k++){
sets[j].push_back(sets[i][k]);
}
sets[i].clear();
}
int main(){
scanf("%d",&n);
sets.assign(n+1,vector<int>());
for(int i=1;i<=n;i++){
p[i]=i;
sets[i].push_back(i);
}
for(int i=1;i<n;i++){
int u,v;
long long w;
cin>>u>>v>>w;
E.push_back(edge(u,v,w));
}
sort(E.begin(),E.end(),cmp);
reverse(E.begin(),E.end());
for(int i=0;i<E.size();i++){
int u=p[E[i].u];
int v=p[E[i].v];
int w=E[i].w;
if(sets[u].size()>sets[v].size()){
swap(u,v);
}
lazy[v]+=w*sets[u].size();
dsu(u,v,w);
}
for(int i=1;i<=n;i++){
cout<<res[i]+lazy[p[i]]<<"\n";
}
}
Submission Info
Submission Time
2018-06-14 19:14:28+0900
Task
E - Black Cats Deployment
User
vjudge3
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1046 Byte
Status
AC
Exec Time
152 ms
Memory
14448 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:27:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
Judge Result
Set Name
Sample
Subtask1
Subtask2
All
Score / Max Score
0 / 0
200 / 200
200 / 200
400 / 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
AC
1 ms
256 KB
00_example_02.txt
AC
1 ms
256 KB
00_example_03.txt
AC
1 ms
256 KB
s1_01.txt
AC
2 ms
384 KB
s1_02.txt
AC
2 ms
384 KB
s1_03.txt
AC
2 ms
256 KB
s1_04.txt
AC
2 ms
384 KB
s1_05.txt
AC
2 ms
384 KB
s1_06.txt
AC
2 ms
384 KB
s1_07.txt
AC
1 ms
256 KB
s2_08.txt
AC
94 ms
9968 KB
s2_09.txt
AC
46 ms
4980 KB
s2_10.txt
AC
26 ms
3068 KB
s2_11.txt
AC
111 ms
11120 KB
s2_12.txt
AC
110 ms
11120 KB
s2_13.txt
AC
112 ms
12272 KB
s2_14.txt
AC
109 ms
13040 KB
s3_15.txt
AC
124 ms
10736 KB
s3_16.txt
AC
61 ms
5620 KB
s3_17.txt
AC
34 ms
3196 KB
s3_18.txt
AC
60 ms
5368 KB
s3_19.txt
AC
142 ms
12144 KB
s3_20.txt
AC
146 ms
12528 KB
s3_21.txt
AC
147 ms
12016 KB
s3_22.txt
AC
147 ms
12016 KB
s3_23.txt
AC
152 ms
14448 KB
s3_24.txt
AC
146 ms
13936 KB
s3_25.txt
AC
128 ms
10864 KB
s3_26.txt
AC
144 ms
13680 KB
s3_27.txt
AC
124 ms
10864 KB
s3_28.txt
AC
146 ms
13680 KB
s3_29.txt
AC
131 ms
10864 KB