Submission #1857134
Source Code Expand
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<unordered_map> #include<array> #include<map> #include<bitset> #include<iomanip> using namespace std; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase //ios::sync_with_stdio(false); //std::cin.tie(0); //<< setprecision(20) const int mod=1e9+7; const llint big=1e15+100; const long double pai=3.141592653589793238462643383279502884197; const long double ena=2.71828182845904523536; const long double eps=1e-7; 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;}} template <class T> void soun(T& ar) {sort(ar.begin(),ar.end());ar.erase(unique(ar.begin(),ar.end()),ar.end());} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){return a/gcd(a,b)*b;} int n; vector<int>oya; vector<vector<int>>ko; vector<int>siz; vector<llint>wa; vector<llint>naga; vector<pair<int,int>> henban; int make_tree(int ter,int per){ if(per!=-1){ko[ter].era(find(ko[ter].begin(),ko[ter].end(),per));} oya[ter]=per; int kos=1; for(auto it:ko[ter]){kos+=make_tree(it,ter);} siz[ter]=kos; return kos; } int main(void){ int i; cin>>n; oya.res(n); ko.res(n); siz.res(n); wa.res(n); naga.res(n); henban.res(n-1); for(int i=0;i<n-1;i++){ int a,b;cin>>a>>b;a--;b--; henban[i]=mp(a,b); ko[a].pub(b); ko[b].pub(a); } for(int i=0;i<n;i++){cin>>wa[i];} make_tree(0,-1); int wakaran=-1; for(i=1;i<n;i++){//0は親のため除く if(siz[i]+siz[i]==n){wakaran=i;continue;} naga[i]=(wa[i]-wa[oya[i]])/(n-siz[i]-siz[i]); } if(wakaran!=-1){ llint nok=wa[wakaran]; for(i=1;i<n;i++){nok-=siz[i]*naga[i];} int now=oya[wakaran]; while(now!=0){nok-=(n-siz[now]-siz[now])*naga[now];now=oya[now];} naga[wakaran]=nok/(n/2); } for(i=0;i<n-1;i++){ int a,b;a=henban[i].fir;b=henban[i].sec; if(oya[a]!=b){swap(a,b);} cout<<naga[a]<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Ancient Tree Record |
User | WA_TLE |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 2452 Byte |
Status | AC |
Exec Time | 311 ms |
Memory | 14080 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 300 / 300 | 200 / 200 | 300 / 300 | ||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.txt, 00_example_03.txt |
Subtask1 | 00_example_01.txt, s1_01.txt, s1_02.txt, s1_03.txt, s1_04.txt, s1_05.txt, s1_06.txt, s1_07.txt, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt |
Subtask2 | 00_example_02.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.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, s1_08.txt, s1_09.txt, s1_10.txt, s1_11.txt, s1_12.txt, s1_13.txt, s2_14.txt, s2_15.txt, s2_16.txt, s2_17.txt, s2_18.txt, s2_19.txt, s2_20.txt, s2_21.txt, s2_22.txt, s2_23.txt, s3_24.txt, s3_25.txt, s3_26.txt, s3_27.txt, s3_28.txt, s3_29.txt, s3_30.txt, s3_31.txt, s3_32.txt, s3_33.txt, s3_34.txt, s3_35.txt, s3_36.txt, s3_37.txt, s3_38.txt, s3_39.txt, s3_40.txt, s3_41.txt, s3_42.txt, s3_43.txt, s3_44.txt, s3_45.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 | 169 ms | 8064 KB |
s1_02.txt | AC | 249 ms | 11264 KB |
s1_03.txt | AC | 11 ms | 768 KB |
s1_04.txt | AC | 199 ms | 9344 KB |
s1_05.txt | AC | 32 ms | 1664 KB |
s1_06.txt | AC | 310 ms | 14080 KB |
s1_07.txt | AC | 302 ms | 14080 KB |
s1_08.txt | AC | 302 ms | 14080 KB |
s1_09.txt | AC | 1 ms | 256 KB |
s1_10.txt | AC | 1 ms | 256 KB |
s1_11.txt | AC | 1 ms | 256 KB |
s1_12.txt | AC | 1 ms | 256 KB |
s1_13.txt | AC | 1 ms | 256 KB |
s2_14.txt | AC | 154 ms | 5756 KB |
s2_15.txt | AC | 220 ms | 7928 KB |
s2_16.txt | AC | 274 ms | 9976 KB |
s2_17.txt | AC | 278 ms | 9976 KB |
s2_18.txt | AC | 276 ms | 9976 KB |
s2_19.txt | AC | 277 ms | 9976 KB |
s2_20.txt | AC | 1 ms | 256 KB |
s2_21.txt | AC | 1 ms | 256 KB |
s2_22.txt | AC | 1 ms | 256 KB |
s2_23.txt | AC | 1 ms | 256 KB |
s3_24.txt | AC | 170 ms | 5504 KB |
s3_25.txt | AC | 245 ms | 7680 KB |
s3_26.txt | AC | 11 ms | 512 KB |
s3_27.txt | AC | 201 ms | 6400 KB |
s3_28.txt | AC | 32 ms | 1280 KB |
s3_29.txt | AC | 309 ms | 9472 KB |
s3_30.txt | AC | 311 ms | 9728 KB |
s3_31.txt | AC | 309 ms | 9472 KB |
s3_32.txt | AC | 308 ms | 12032 KB |
s3_33.txt | AC | 311 ms | 13440 KB |
s3_34.txt | AC | 302 ms | 9976 KB |
s3_35.txt | AC | 296 ms | 9976 KB |
s3_36.txt | AC | 1 ms | 256 KB |
s3_37.txt | AC | 1 ms | 256 KB |
s3_38.txt | AC | 1 ms | 256 KB |
s3_39.txt | AC | 1 ms | 256 KB |
s3_40.txt | AC | 170 ms | 5632 KB |
s3_41.txt | AC | 242 ms | 7680 KB |
s3_42.txt | AC | 11 ms | 512 KB |
s3_43.txt | AC | 303 ms | 9472 KB |
s3_44.txt | AC | 306 ms | 9728 KB |
s3_45.txt | AC | 306 ms | 9472 KB |