Submission #3321136
Source Code Expand
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long ll; int N,A[100010],B[100010],E[100010] = {0},visited[200010] = {0}; ll C[100010],ans[200010] = {0}; vector<pair<ll,int>> e; vector<vector<pair<ll,int>>> v(200010); int p[100010] = {0},r[200010] = {0}; ll s[100010] = {0}; void init(int N){ for(int i=0;i<=N;++i){ p[i] = i; s[i] = 1; E[i] = i; } } int root(int a){ if(p[a] == a) return a; return (p[a] = root(p[a])); } bool is_same_set(int a,int b){ return root(a) == root(b); } void unite(int a, int b){ a = root(a); b = root(b); if(a==b) return; if(r[a]<r[b]){ p[a] = b; s[b] += s[a]; s[a] = s[b]; }else{ p[b] = a; s[a] += s[b]; s[b] = s[a]; if(r[a] == r[b]) r[a]++; } } void dfs(int n){ visited[n] = 1; for(int i=0;i<v[n].size();i++){ int t = v[n][i].second,cost = v[n][i].first; if(visited[t]==0){ ans[t] = ans[n] + cost; dfs(t); } } } int main(){ cin >> N; init(N); for(int i=1;i<=N-1;i++){ cin >> A[i] >> B[i] >> C[i]; e.push_back({C[i],i}); } sort(e.begin(),e.end()); for(int i=N-2;i>=0;i--){ int t = e[i].second; ll cost = e[i].first; v[t+N].push_back({cost*s[root(B[t])],E[root(A[t])]}); E[root(A[t])] = t+N; v[t+N].push_back({cost*s[root(A[t])],E[root(B[t])]}); E[root(B[t])] = t+N; unite(A[t],B[t]); } dfs(N+e[0].second); for(int i=1;i<=N;i++){ cout << ans[i] << endl; } }
Submission Info
Submission Time | |
---|---|
Task | E - Black Cats Deployment |
User | idsigma |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 1493 Byte |
Status | RE |
Exec Time | 304 ms |
Memory | 21232 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 200 | 0 / 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 | 4 ms | 9088 KB |
00_example_02.txt | AC | 3 ms | 9088 KB |
00_example_03.txt | AC | 4 ms | 9088 KB |
s1_01.txt | WA | 4 ms | 9088 KB |
s1_02.txt | WA | 5 ms | 9088 KB |
s1_03.txt | WA | 5 ms | 9088 KB |
s1_04.txt | WA | 6 ms | 9216 KB |
s1_05.txt | WA | 6 ms | 9088 KB |
s1_06.txt | WA | 7 ms | 9088 KB |
s1_07.txt | RE | 98 ms | 7040 KB |
s2_08.txt | AC | 242 ms | 16624 KB |
s2_09.txt | AC | 119 ms | 12788 KB |
s2_10.txt | AC | 70 ms | 11256 KB |
s2_11.txt | AC | 270 ms | 17776 KB |
s2_12.txt | AC | 270 ms | 17648 KB |
s2_13.txt | AC | 265 ms | 19312 KB |
s2_14.txt | AC | 262 ms | 17520 KB |
s3_15.txt | WA | 265 ms | 17648 KB |
s3_16.txt | WA | 135 ms | 13172 KB |
s3_17.txt | WA | 78 ms | 11640 KB |
s3_18.txt | WA | 134 ms | 13428 KB |
s3_19.txt | WA | 297 ms | 18800 KB |
s3_20.txt | WA | 299 ms | 18416 KB |
s3_21.txt | WA | 304 ms | 18928 KB |
s3_22.txt | WA | 303 ms | 18928 KB |
s3_23.txt | WA | 301 ms | 18160 KB |
s3_24.txt | WA | 296 ms | 18160 KB |
s3_25.txt | WA | 287 ms | 21232 KB |
s3_26.txt | WA | 292 ms | 18160 KB |
s3_27.txt | WA | 291 ms | 21232 KB |
s3_28.txt | WA | 291 ms | 18160 KB |
s3_29.txt | WA | 290 ms | 21232 KB |