Submission #1837082
Source Code Expand
#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
template<class T>
struct ICAdd {
std::vector<T> val;
std::vector<int> l;
std::vector<int> r;
std::vector<int> uf;
std::vector<int> uf2;
ICAdd(int n) : l(n, -1), r(n, -1), val(n), uf(n, -1), uf2(n) {
for (int i = 0; i < n; i++) {
uf2[i] = i;
}
}
int find(int u) {
if (uf[u] < 0) return u;
return uf[u] = find(uf[u]);
}
void merge(int u, int v) {
u = find(u);
v = find(v);
if (u == v) return;
if (-uf[u] < -uf[v]) std::swap(u, v);
uf[u] += uf[v];
uf[v] = u;
val.push_back(T());
l.push_back(uf2[u]);
r.push_back(uf2[v]);
uf2[u] = l.size() - 1;
}
void add(int u, T x) {
val[uf2[find(u)]] += x;
}
int size(int u) {
return -uf[find(u)];
}
void dfs(int u, T x) {
if (u == -1) return;
val[u] += x;
dfs(l[u], val[u]);
dfs(r[u], val[u]);
}
void build() {
std::vector<bool> used(l.size());
for (int i = l.size() - 1; i >= 0; i--) {
if (l[i] != -1) used[l[i]] = true;
if (r[i] != -1) used[r[i]] = true;
if (!used[i]) {
dfs(i, T());
}
}
}
};
int main() {
using namespace std;
cin.tie(0);
ios::sync_with_stdio(false);
int n;
cin >> n;
vector<tuple<int, int, int>> es;
for (int i = 0; i < n - 1; i++) {
int u, v, w;
cin >> u >> v >> w;
u--;
v--;
es.emplace_back(w, u, v);
}
sort(es.begin(), es.end());
reverse(es.begin(), es.end());
ICAdd<long long> ic(n);
for (auto e : es) {
int w, u, v;
tie(w, u, v) = e;
long long x = ic.size(u);
long long y = ic.size(v);
ic.add(u, y*w);
ic.add(v, x*w);
ic.merge(u, v);
}
ic.build();
for (int i = 0; i < n; i++) {
cout << ic.val[i] << endl;
}
}
Submission Info
Submission Time |
|
Task |
E - Black Cats Deployment |
User |
pekempey |
Language |
C++14 (GCC 5.4.1) |
Score |
800 |
Code Size |
1919 Byte |
Status |
AC |
Exec Time |
195 ms |
Memory |
8676 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 |
2 ms |
256 KB |
s1_02.txt |
AC |
2 ms |
256 KB |
s1_03.txt |
AC |
2 ms |
256 KB |
s1_04.txt |
AC |
3 ms |
384 KB |
s1_05.txt |
AC |
3 ms |
384 KB |
s1_06.txt |
AC |
3 ms |
384 KB |
s1_07.txt |
AC |
1 ms |
256 KB |
s2_08.txt |
AC |
165 ms |
6004 KB |
s2_09.txt |
AC |
84 ms |
3064 KB |
s2_10.txt |
AC |
49 ms |
1972 KB |
s2_11.txt |
AC |
188 ms |
6884 KB |
s2_12.txt |
AC |
189 ms |
6884 KB |
s2_13.txt |
AC |
190 ms |
6756 KB |
s2_14.txt |
AC |
188 ms |
6756 KB |
s3_15.txt |
AC |
169 ms |
6772 KB |
s3_16.txt |
AC |
85 ms |
3448 KB |
s3_17.txt |
AC |
50 ms |
2100 KB |
s3_18.txt |
AC |
85 ms |
3576 KB |
s3_19.txt |
AC |
192 ms |
7652 KB |
s3_20.txt |
AC |
193 ms |
7524 KB |
s3_21.txt |
AC |
193 ms |
7780 KB |
s3_22.txt |
AC |
195 ms |
7780 KB |
s3_23.txt |
AC |
193 ms |
7268 KB |
s3_24.txt |
AC |
189 ms |
7396 KB |
s3_25.txt |
AC |
187 ms |
8676 KB |
s3_26.txt |
AC |
187 ms |
7396 KB |
s3_27.txt |
AC |
188 ms |
8676 KB |
s3_28.txt |
AC |
187 ms |
7396 KB |
s3_29.txt |
AC |
186 ms |
8676 KB |