Submission #3334869
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }
struct QU {
V<> par, rank, _size;
V<lint> res;
QU(int n) : par(n), rank(n), _size(n, 1), res(n) {
iota(par.begin(), par.end(), 0);
}
int find(int a) {
if (par[a] == a) return a;
return find(par[a]);
}
bool same(int a, int b) { return find(a) == find(b); }
int size(int a) { return _size[find(a)]; }
void unite(int a, int b, lint c) {
a = find(a), b = find(b);
if (a == b) return;
if (rank[a] < rank[b]) {
res[b] += _size[a] * c;
res[a] += _size[b] * c - res[b];
par[a] = b;
_size[b] += _size[a];
} else {
res[a] += _size[b] * c;
res[b] += _size[a] * c - res[a];
par[b] = a;
_size[a] += _size[b];
}
if (rank[a] == rank[b]) rank[a]++;
}
};
int main() {
cin.tie(NULL); ios::sync_with_stdio(false);
int n; cin >> n;
struct edge { int from, to; lint c; };
V<edge> es(n - 1);
for (int i = 0; i < n - 1; i++) {
int a, b, c; cin >> a >> b >> c, a--, b--;
es[i] = {a, b, c};
}
sort(es.begin(), es.end(), [](edge x, edge y) { return x.c > y.c; });
QU qu(n);
for (auto&& e : es) qu.unite(e.from, e.to, e.c);
VV<> ch(n);
int root = qu.find(0);
for (int v = 0; v < n; v++) if (v != root) ch[qu.par[v]].push_back(v);
queue<int> que;
que.push(root);
while (!que.empty()) {
int v = que.front(); que.pop();
for (int w : ch[v]) {
qu.res[w] += qu.res[v]; que.push(w);
}
}
for (int i = 0; i < n; i++) cout << qu.res[i] << '\n';
}
Submission Info
Submission Time |
|
Task |
E - Black Cats Deployment |
User |
risujiroh |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1923 Byte |
Status |
AC |
Exec Time |
57 ms |
Memory |
8704 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 |
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 |
1 ms |
256 KB |
s1_02.txt |
AC |
1 ms |
256 KB |
s1_03.txt |
AC |
1 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 |
39 ms |
6912 KB |
s2_09.txt |
AC |
20 ms |
3584 KB |
s2_10.txt |
AC |
12 ms |
2176 KB |
s2_11.txt |
AC |
44 ms |
7936 KB |
s2_12.txt |
AC |
46 ms |
8064 KB |
s2_13.txt |
AC |
46 ms |
8064 KB |
s2_14.txt |
AC |
39 ms |
7680 KB |
s3_15.txt |
AC |
48 ms |
7552 KB |
s3_16.txt |
AC |
25 ms |
3968 KB |
s3_17.txt |
AC |
14 ms |
2432 KB |
s3_18.txt |
AC |
24 ms |
3968 KB |
s3_19.txt |
AC |
56 ms |
8704 KB |
s3_20.txt |
AC |
55 ms |
8704 KB |
s3_21.txt |
AC |
56 ms |
8704 KB |
s3_22.txt |
AC |
56 ms |
8704 KB |
s3_23.txt |
AC |
57 ms |
8576 KB |
s3_24.txt |
AC |
52 ms |
8576 KB |
s3_25.txt |
AC |
43 ms |
8440 KB |
s3_26.txt |
AC |
50 ms |
8576 KB |
s3_27.txt |
AC |
43 ms |
8440 KB |
s3_28.txt |
AC |
48 ms |
8576 KB |
s3_29.txt |
AC |
43 ms |
8440 KB |