Submission #3386510
Source Code Expand
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <string> #include <sstream> #include <complex> #include <vector> #include <list> #include <queue> #include <deque> #include <stack> #include <map> #include <set> using namespace std; #define mod 1000000007 #define FOR(x,to) for(int x=0;x<(to);x++) #define FORR(x,arr) for(auto& x:arr) #define ALL(a) (a.begin()),(a.end()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define long long long inline int rei(){int x;cin>>x;return x;} inline long rel(){long x;cin>>x;return x;} inline string res(){string x;cin>>x;return x;} //------------------------------------------------------- vector<tuple<int,long,int,int>> G[100000]; long S[100000]; int child[100000]; long ans[99999]; long sumcost[100000]; void Calc(){ int N = rei(); for(int i=0;i<N-1;i++){ int a = rei()-1; int b = rei()-1; G[a].push_back({b,0,i,G[b].size()}); G[b].push_back({a,0,i,G[a].size()-1}); } for(int i=0;i<N;i++){ S[i] = rel(); } stack<pair<int,int>> sp; sp.push({0,-1}); while(!sp.empty()){ int v = sp.top().first; int f = sp.top().second; sp.pop(); if(v >= N){ v -= N; child[v] = 1; for(int i=0;i<G[v].size();i++){ int t = get<0>(G[v][i]); if(t != f){ child[v] += child[t]; } } } else{ sp.push({v+N,f}); for(int i=0;i<G[v].size();i++){ int t = get<0>(G[v][i]); if(t != f){ sp.push({t,v}); } } } } int halfchild1 = -1; int halfchild2 = -1; int halfedge = -1; stack<tuple<int,int,int>> sp2; sp2.push({0,-1,-1}); while(!sp2.empty()){ int v = get<0>(sp2.top()); int f = get<1>(sp2.top()); int fe = get<2>(sp2.top()); sp2.pop(); if(f != -1){ if(child[v]*2 == N){ halfchild1 = f; halfchild2 = v; halfedge = get<2>(G[f][fe]); } else{ long cost = (S[v] - S[f]) / (N - child[v]*2); ans[get<2>(G[f][fe])] = cost; G[f][fe] = {get<0>(G[f][fe]),cost,get<2>(G[f][fe]),get<3>(G[f][fe])}; int fe2 = get<3>(G[f][fe]); G[v][fe2] = {get<0>(G[v][fe2]),cost,get<2>(G[v][fe2]),get<3>(G[v][fe2])}; } } for(int i=0;i<G[v].size();i++){ int t = get<0>(G[v][i]); if(t != f){ sp2.push({t,v,i}); } } } if(halfchild1 != -1){ sp.push({halfchild1,-1}); while(!sp.empty()){ int v = sp.top().first; int f = sp.top().second; sp.pop(); if(v >= N){ v -= N; child[v] = 1; for(int i=0;i<G[v].size();i++){ int t = get<0>(G[v][i]); if(t != f){ sumcost[v] += sumcost[t] + get<1>(G[v][i])*child[t]; child[v] += child[t]; } } } else{ sp.push({v+N,f}); for(int i=0;i<G[v].size();i++){ int t = get<0>(G[v][i]); if(t != f){ sp.push({t,v}); } } } } ans[halfedge] = (S[halfchild1]-sumcost[halfchild1]) / (child[halfchild1] - 1); } for(int i=0;i<N-1;i++){ cout << ans[i] << endl; } } int main(int argc,char** argv){ ios::sync_with_stdio(false), cin.tie(0); cout.tie(0); Calc(); return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Ancient Tree Record |
User | leign |
Language | C++14 (Clang 3.8.0) |
Score | 200 |
Code Size | 3171 Byte |
Status | WA |
Exec Time | 576 ms |
Memory | 12928 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 300 | 200 / 200 | 0 / 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 | WA | 2 ms | 4352 KB |
00_example_02.txt | AC | 3 ms | 4352 KB |
00_example_03.txt | AC | 3 ms | 4352 KB |
s1_01.txt | WA | 302 ms | 9032 KB |
s1_02.txt | AC | 428 ms | 10496 KB |
s1_03.txt | WA | 20 ms | 4608 KB |
s1_04.txt | AC | 352 ms | 9344 KB |
s1_05.txt | AC | 56 ms | 5120 KB |
s1_06.txt | AC | 545 ms | 12016 KB |
s1_07.txt | WA | 540 ms | 12784 KB |
s1_08.txt | AC | 538 ms | 12016 KB |
s1_09.txt | AC | 2 ms | 4352 KB |
s1_10.txt | WA | 2 ms | 4352 KB |
s1_11.txt | AC | 2 ms | 4352 KB |
s1_12.txt | WA | 3 ms | 4352 KB |
s1_13.txt | AC | 3 ms | 4352 KB |
s2_14.txt | AC | 278 ms | 8500 KB |
s2_15.txt | AC | 392 ms | 11312 KB |
s2_16.txt | AC | 490 ms | 11952 KB |
s2_17.txt | AC | 490 ms | 11952 KB |
s2_18.txt | AC | 493 ms | 12336 KB |
s2_19.txt | AC | 496 ms | 12464 KB |
s2_20.txt | AC | 2 ms | 4352 KB |
s2_21.txt | AC | 3 ms | 4352 KB |
s2_22.txt | AC | 3 ms | 4352 KB |
s2_23.txt | AC | 2 ms | 4352 KB |
s3_24.txt | AC | 301 ms | 8320 KB |
s3_25.txt | AC | 431 ms | 10112 KB |
s3_26.txt | AC | 20 ms | 4608 KB |
s3_27.txt | AC | 359 ms | 9088 KB |
s3_28.txt | AC | 56 ms | 5120 KB |
s3_29.txt | AC | 543 ms | 11776 KB |
s3_30.txt | AC | 534 ms | 11776 KB |
s3_31.txt | AC | 546 ms | 11648 KB |
s3_32.txt | WA | 558 ms | 12604 KB |
s3_33.txt | AC | 576 ms | 12004 KB |
s3_34.txt | AC | 532 ms | 11952 KB |
s3_35.txt | AC | 531 ms | 12592 KB |
s3_36.txt | WA | 3 ms | 4352 KB |
s3_37.txt | AC | 3 ms | 4352 KB |
s3_38.txt | AC | 3 ms | 4352 KB |
s3_39.txt | AC | 3 ms | 4352 KB |
s3_40.txt | WA | 304 ms | 8832 KB |
s3_41.txt | WA | 440 ms | 10752 KB |
s3_42.txt | WA | 20 ms | 4608 KB |
s3_43.txt | WA | 560 ms | 12544 KB |
s3_44.txt | WA | 552 ms | 12544 KB |
s3_45.txt | WA | 557 ms | 12928 KB |