Submission #2137752
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> #include <utility> #define llint long long using namespace std; struct Node{ int left, right; llint val; Node(){ left = right = -1; } Node(int a, int b, llint c){ left = a, right = b, val = c; } }; int N; int id[100005]; vector< pair< int, pair<int, int> > > edge; vector<Node> tree; int num[200005]; llint ans[100005]; int parent[100005]; void init() { for(int i = 1; i <= N; i++) parent[i] = i; } int root(int i) { if(parent[i] == i) return i; return parent[i] = root(parent[i]); } bool same(int i, int j) { return root(i) == root(j); } void unite(int i, int j) { int root_i = root(i), root_j = root(j); if(root_i == root_j) return; parent[root_i] = root_j; } int dfs(int v) { int ret = 0; if(tree[v].left != -1){ ret += dfs(tree[v].left); ret += dfs(tree[v].right); } else ret = 1; return num[v] = ret; } void dfs2(int v, llint sum) { if(tree[v].left != -1){ dfs2(tree[v].left, sum + num[tree[v].right] * tree[v].val); dfs2(tree[v].right, sum + num[tree[v].left] * tree[v].val); } else{ ans[v+1] = sum; } } int main(void) { cin >> N; init(); for(int i = 1; i <= N; i++) id[i] = i-1; for(int i = 0; i < N; i++) tree.push_back( Node() ); int a, b; llint c; for(int i = 0; i < N-1; i++){ cin >> a >> b >> c; edge.push_back(make_pair(c, make_pair(a, b))); } sort(edge.begin(), edge.end()); reverse(edge.begin(), edge.end()); for(int i = 0; i < edge.size(); i++){ a = edge[i].second.first, b = edge[i].second.second, c = edge[i].first; tree.push_back(Node()); tree.back().left = id[root(a)]; tree.back().right = id[root(b)]; tree.back().val = c; unite(a, b); id[root(a)] = tree.size()-1; } int s = id[root(1)]; dfs(s); dfs2(s, 0); for(int i = 1; i <= N; i++){ cout << ans[i] << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Black Cats Deployment |
User | leaf1415 |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1949 Byte |
Status | AC |
Exec Time | 294 ms |
Memory | 13932 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 | 3 ms | 384 KB |
s1_02.txt | AC | 3 ms | 384 KB |
s1_03.txt | AC | 2 ms | 256 KB |
s1_04.txt | AC | 4 ms | 384 KB |
s1_05.txt | AC | 4 ms | 384 KB |
s1_06.txt | AC | 4 ms | 384 KB |
s1_07.txt | AC | 1 ms | 256 KB |
s2_08.txt | AC | 232 ms | 8556 KB |
s2_09.txt | AC | 114 ms | 4208 KB |
s2_10.txt | AC | 66 ms | 2676 KB |
s2_11.txt | AC | 264 ms | 9580 KB |
s2_12.txt | AC | 266 ms | 9324 KB |
s2_13.txt | AC | 261 ms | 9836 KB |
s2_14.txt | AC | 267 ms | 10092 KB |
s3_15.txt | AC | 253 ms | 9324 KB |
s3_16.txt | AC | 126 ms | 4592 KB |
s3_17.txt | AC | 74 ms | 2804 KB |
s3_18.txt | AC | 126 ms | 4848 KB |
s3_19.txt | AC | 291 ms | 10348 KB |
s3_20.txt | AC | 294 ms | 10732 KB |
s3_21.txt | AC | 289 ms | 10348 KB |
s3_22.txt | AC | 288 ms | 10348 KB |
s3_23.txt | AC | 284 ms | 9580 KB |
s3_24.txt | AC | 287 ms | 10348 KB |
s3_25.txt | AC | 287 ms | 13036 KB |
s3_26.txt | AC | 283 ms | 9708 KB |
s3_27.txt | AC | 284 ms | 13292 KB |
s3_28.txt | AC | 281 ms | 9836 KB |
s3_29.txt | AC | 285 ms | 13932 KB |