Submission #1833382
Source Code Expand
#include <bits/stdc++.h>
#define FIO "race"
#define mset(a,b) memset(a,b,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof b)
#define xx first
#define yy second
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define lb(x) ((x)&(-(x)))
#define dalao 1000000007
#define inf 0x3f3f3f3f
#define N 200010
using namespace std;
typedef long long ll;
struct edge{int a,b,c;bool operator <(const edge& t)const{return c>t.c;};}e[N];
int n,cnt,fa[N],siz[N],v[N],G[N][2];
ll ans[N];
inline int find(int x){while(x^fa[x])x=fa[x]=fa[fa[x]];return x;}
inline void dfs(int x,ll t){
if(x<=n){ans[x]=t;return;}
dfs(G[x][0],t+1ll*v[x]*siz[G[x][1]]),dfs(G[x][1],t+1ll*v[x]*siz[G[x][0]]);
}
int main(){
cin>>n,cnt=n;
for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1;
for(int i=1;i<n;i++)scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+n);
for(int i=1;i<n;i++){
int x=find(e[i].a),y=find(e[i].b);
cnt++,fa[cnt]=cnt,v[cnt]=e[i].c,siz[cnt]=siz[x]+siz[y],fa[x]=fa[y]=cnt;
G[cnt][0]=x,G[cnt][1]=y;
}
dfs(cnt,0);
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
return 0;
}
Submission Info
Submission Time
2017-12-04 23:16:44+0900
Task
E - Black Cats Deployment
User
cdsfcesf
Language
C++14 (GCC 5.4.1)
Score
800
Code Size
1107 Byte
Status
AC
Exec Time
58 ms
Memory
7936 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:27:61: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<n;i++)scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
^
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
2 ms
4352 KB
00_example_02.txt
AC
2 ms
4352 KB
00_example_03.txt
AC
2 ms
4352 KB
s1_01.txt
AC
2 ms
4352 KB
s1_02.txt
AC
2 ms
4352 KB
s1_03.txt
AC
3 ms
4352 KB
s1_04.txt
AC
3 ms
4352 KB
s1_05.txt
AC
2 ms
4352 KB
s1_06.txt
AC
3 ms
4352 KB
s1_07.txt
AC
2 ms
4352 KB
s2_08.txt
AC
35 ms
6016 KB
s2_09.txt
AC
18 ms
5120 KB
s2_10.txt
AC
12 ms
4992 KB
s2_11.txt
AC
45 ms
6400 KB
s2_12.txt
AC
42 ms
6400 KB
s2_13.txt
AC
38 ms
6272 KB
s2_14.txt
AC
37 ms
6272 KB
s3_15.txt
AC
45 ms
6656 KB
s3_16.txt
AC
23 ms
5376 KB
s3_17.txt
AC
14 ms
5120 KB
s3_18.txt
AC
24 ms
5504 KB
s3_19.txt
AC
53 ms
7168 KB
s3_20.txt
AC
55 ms
7040 KB
s3_21.txt
AC
52 ms
7168 KB
s3_22.txt
AC
58 ms
7168 KB
s3_23.txt
AC
48 ms
6784 KB
s3_24.txt
AC
47 ms
6912 KB
s3_25.txt
AC
46 ms
7936 KB
s3_26.txt
AC
45 ms
6912 KB
s3_27.txt
AC
46 ms
7936 KB
s3_28.txt
AC
43 ms
6912 KB
s3_29.txt
AC
46 ms
7936 KB