Submission #3321176
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[100010] = {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; ll cost = v[n][i].first; if(visited[t]==0){ ans[t] = ans[n] + cost; dfs(t); } } } int main(){ cin >> N; init(N); if(N==1){ cout << 0 << endl; return 0; } 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])]}); v[t+N].push_back({cost*s[root(A[t])],E[root(B[t])]}); unite(A[t],B[t]); E[root(A[t])] = t+N; } 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 | 800 |
Code Size | 1529 Byte |
Status | AC |
Exec Time | 314 ms |
Memory | 21232 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 | 7040 KB |
00_example_02.txt | AC | 2 ms | 7040 KB |
00_example_03.txt | AC | 3 ms | 7040 KB |
s1_01.txt | AC | 4 ms | 7040 KB |
s1_02.txt | AC | 4 ms | 7040 KB |
s1_03.txt | AC | 5 ms | 7040 KB |
s1_04.txt | AC | 6 ms | 7168 KB |
s1_05.txt | AC | 6 ms | 7168 KB |
s1_06.txt | AC | 5 ms | 7168 KB |
s1_07.txt | AC | 3 ms | 4992 KB |
s2_08.txt | AC | 240 ms | 16368 KB |
s2_09.txt | AC | 118 ms | 11764 KB |
s2_10.txt | AC | 70 ms | 9848 KB |
s2_11.txt | AC | 274 ms | 17776 KB |
s2_12.txt | AC | 273 ms | 17648 KB |
s2_13.txt | AC | 269 ms | 19312 KB |
s2_14.txt | AC | 264 ms | 17520 KB |
s3_15.txt | AC | 264 ms | 17520 KB |
s3_16.txt | AC | 132 ms | 12148 KB |
s3_17.txt | AC | 77 ms | 10232 KB |
s3_18.txt | AC | 134 ms | 12532 KB |
s3_19.txt | AC | 305 ms | 18928 KB |
s3_20.txt | AC | 308 ms | 18544 KB |
s3_21.txt | AC | 310 ms | 19056 KB |
s3_22.txt | AC | 314 ms | 19056 KB |
s3_23.txt | AC | 304 ms | 18160 KB |
s3_24.txt | AC | 296 ms | 18288 KB |
s3_25.txt | AC | 290 ms | 21232 KB |
s3_26.txt | AC | 296 ms | 18288 KB |
s3_27.txt | AC | 291 ms | 21232 KB |
s3_28.txt | AC | 298 ms | 18288 KB |
s3_29.txt | AC | 293 ms | 21232 KB |