Submission #1864837
Source Code Expand
#include<cstdio> #include<algorithm> #include<vector> #include<deque> #include<stack> #include<queue> #include<string> #include<iostream> #include<tuple> #include<utility> #include<set> #include<queue> #include<iomanip> #include<iterator> #include<map> #include<bitset> #include<array> #include<cmath> #include<functional> #include<list> using namespace std; typedef long long int llint; typedef long double lldo; const llint big=2e18+100000; const int mod=1e9+7; const lldo eps=1e-7; const long double pai=3.141592653589793238462643383279502884197; #define mt make_tuple #define mp make_pair #define fir first #define sec second #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define res resize #define ins insert #define era erase #define dme(in) cout<<in<<endl;return 0 template <class T,class U>void mineq(T& a,U b){if(a>b){a=b;}} template <class T,class U>void maxeq(T& a,U b){if(a<b){a=b;}} int main(void){ int i,n;cin>>n; vector<tuple<llint,int,int>>hen(n-1); vector<int>oya(n); vector<int>siz(n,1); vector<llint>imo(n);//下方向 for(i=0;i<n;i++){oya[i]=i;} for(i=0;i<n-1;i++){ int a,b,c;cin>>a>>b>>c;a--;b--; hen[i]=mt(c,a,b); } sort(hen.rbegin(),hen.rend()); //すぬけ 木である必要はない for(i=0;i<n-1;i++){ int a,b;llint c; tie(c,a,b)=hen[i]; while(a!=oya[a]){a=oya[a];} while(b!=oya[b]){b=oya[b];} if(a==b){continue;} if(siz[a]<siz[b]){swap(a,b);} imo[a]+=c*siz[b]; imo[b]+=c*siz[a]-imo[a]; siz[a]+=siz[b]; oya[b]=a; } vector<pair<int,int>>miru(n); for(i=0;i<n;i++){miru[i]=mp(siz[i],i);} //子のほうがサイズが小さいので親から見る=サイズの大きい順 sort(miru.rbegin(),miru.rend()); for(i=1;i<n;i++){//最大は根なので imo[miru[i].sec]+=imo[oya[miru[i].sec]]; } for(i=0;i<n;i++){cout<<imo[i]<<endl;} return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Black Cats Deployment |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1926 Byte |
Status | AC |
Exec Time | 278 ms |
Memory | 5632 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 | 256 KB |
s1_02.txt | AC | 2 ms | 256 KB |
s1_03.txt | AC | 2 ms | 256 KB |
s1_04.txt | AC | 4 ms | 256 KB |
s1_05.txt | AC | 4 ms | 256 KB |
s1_06.txt | AC | 4 ms | 256 KB |
s1_07.txt | AC | 1 ms | 256 KB |
s2_08.txt | AC | 214 ms | 4224 KB |
s2_09.txt | AC | 105 ms | 2176 KB |
s2_10.txt | AC | 62 ms | 1408 KB |
s2_11.txt | AC | 243 ms | 4864 KB |
s2_12.txt | AC | 244 ms | 4864 KB |
s2_13.txt | AC | 244 ms | 4864 KB |
s2_14.txt | AC | 236 ms | 4864 KB |
s3_15.txt | AC | 230 ms | 4864 KB |
s3_16.txt | AC | 115 ms | 2560 KB |
s3_17.txt | AC | 68 ms | 1536 KB |
s3_18.txt | AC | 117 ms | 2560 KB |
s3_19.txt | AC | 278 ms | 5504 KB |
s3_20.txt | AC | 263 ms | 5504 KB |
s3_21.txt | AC | 265 ms | 5504 KB |
s3_22.txt | AC | 267 ms | 5504 KB |
s3_23.txt | AC | 265 ms | 5376 KB |
s3_24.txt | AC | 255 ms | 5376 KB |
s3_25.txt | AC | 265 ms | 5632 KB |
s3_26.txt | AC | 259 ms | 5376 KB |
s3_27.txt | AC | 259 ms | 5632 KB |
s3_28.txt | AC | 258 ms | 5376 KB |
s3_29.txt | AC | 257 ms | 5632 KB |