Submission #1840713
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)
const int MC = 100010;
int N;
tuple<LL,int,int> e[MC];
LL ans[MC];
LL potential[MC];
int group[MC];
vector<int> G[MC];
void uni(int a , int b){
int x = group[a] , y = group[b];
if(G[x].size() < G[y].size()) swap(x,y);
for(auto u : G[y]){
ans[u] += potential[y] - potential[x];
G[x].PB(u);
group[u] = x;
}
}
int main(){
cin >> N;
repp(i,1,N+1){
G[i].PB(i);
group[i] = i;
}
repp(i,1,N){
int a,b,c;
cin >> a >> b >> c;
e[i-1] = make_tuple(c,a,b);
}
sort(e,e+N-1);
repm(i,N-2,-1){
int a = get<1>(e[i]) , b = get<2>(e[i]) , c = get<0>(e[i]);
potential[group[a]] += c * G[group[b]].size();
potential[group[b]] += c * G[group[a]].size();
uni(a,b);
}
repp(i,1,N+1) cout << ans[i] + potential[group[i]] << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Black Cats Deployment |
User |
PIandS |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1336 Byte |
Status |
AC |
Exec Time |
318 ms |
Memory |
13944 KB |
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 |
3 ms |
4352 KB |
00_example_02.txt |
AC |
3 ms |
4352 KB |
00_example_03.txt |
AC |
3 ms |
4352 KB |
s1_01.txt |
AC |
4 ms |
4352 KB |
s1_02.txt |
AC |
4 ms |
4352 KB |
s1_03.txt |
AC |
4 ms |
4352 KB |
s1_04.txt |
AC |
5 ms |
4352 KB |
s1_05.txt |
AC |
5 ms |
4352 KB |
s1_06.txt |
AC |
5 ms |
4480 KB |
s1_07.txt |
AC |
3 ms |
4352 KB |
s2_08.txt |
AC |
238 ms |
11768 KB |
s2_09.txt |
AC |
119 ms |
7420 KB |
s2_10.txt |
AC |
68 ms |
6016 KB |
s2_11.txt |
AC |
273 ms |
11000 KB |
s2_12.txt |
AC |
274 ms |
11512 KB |
s2_13.txt |
AC |
281 ms |
13304 KB |
s2_14.txt |
AC |
277 ms |
13564 KB |
s3_15.txt |
AC |
273 ms |
10940 KB |
s3_16.txt |
AC |
134 ms |
7676 KB |
s3_17.txt |
AC |
78 ms |
6272 KB |
s3_18.txt |
AC |
134 ms |
7420 KB |
s3_19.txt |
AC |
311 ms |
11768 KB |
s3_20.txt |
AC |
309 ms |
12280 KB |
s3_21.txt |
AC |
311 ms |
11768 KB |
s3_22.txt |
AC |
307 ms |
11768 KB |
s3_23.txt |
AC |
318 ms |
13944 KB |
s3_24.txt |
AC |
307 ms |
13560 KB |
s3_25.txt |
AC |
295 ms |
11256 KB |
s3_26.txt |
AC |
306 ms |
13372 KB |
s3_27.txt |
AC |
298 ms |
11256 KB |
s3_28.txt |
AC |
307 ms |
13304 KB |
s3_29.txt |
AC |
294 ms |
11256 KB |