Submission #3386453
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; 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]); } } } 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 | C - Paired Parentheses |
User | leign |
Language | C++14 (Clang 3.8.0) |
Score | 0 |
Code Size | 3114 Byte |
Status | RE |
Exec Time | 105 ms |
Memory | 4736 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | All | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 200 | 0 / 300 | 0 / 200 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Sample | 00_example_01.txt, 00_example_02.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 | 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, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_28.txt |
All | 00_example_01.txt, 00_example_02.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, s2_24.txt, s2_25.txt, s2_26.txt, s2_27.txt, s2_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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
00_example_01.txt | WA | 5 ms | 4480 KB |
00_example_02.txt | RE | 105 ms | 4736 KB |
s1_01.txt | RE | 100 ms | 4352 KB |
s1_02.txt | WA | 3 ms | 4352 KB |
s1_03.txt | RE | 97 ms | 4352 KB |
s1_04.txt | WA | 3 ms | 4352 KB |
s1_05.txt | RE | 97 ms | 4352 KB |
s1_06.txt | RE | 97 ms | 4352 KB |
s1_07.txt | RE | 97 ms | 4352 KB |
s1_08.txt | RE | 98 ms | 4352 KB |
s1_09.txt | RE | 97 ms | 4352 KB |
s1_10.txt | RE | 97 ms | 4352 KB |
s1_11.txt | WA | 2 ms | 4352 KB |
s1_12.txt | WA | 2 ms | 4352 KB |
s1_13.txt | WA | 2 ms | 4352 KB |
s2_14.txt | RE | 97 ms | 4352 KB |
s2_15.txt | RE | 97 ms | 4352 KB |
s2_16.txt | RE | 97 ms | 4352 KB |
s2_17.txt | RE | 97 ms | 4352 KB |
s2_18.txt | RE | 97 ms | 4352 KB |
s2_19.txt | RE | 96 ms | 4352 KB |
s2_20.txt | RE | 97 ms | 4352 KB |
s2_21.txt | RE | 97 ms | 4352 KB |
s2_22.txt | RE | 100 ms | 4352 KB |
s2_23.txt | RE | 100 ms | 4352 KB |
s2_24.txt | RE | 97 ms | 4352 KB |
s2_25.txt | RE | 97 ms | 4352 KB |
s2_26.txt | RE | 96 ms | 4352 KB |
s2_27.txt | RE | 97 ms | 4352 KB |
s2_28.txt | RE | 97 ms | 4352 KB |
s3_29.txt | RE | 100 ms | 4352 KB |
s3_30.txt | RE | 97 ms | 4352 KB |
s3_31.txt | RE | 97 ms | 4352 KB |
s3_32.txt | RE | 99 ms | 4352 KB |
s3_33.txt | RE | 101 ms | 4352 KB |
s3_34.txt | RE | 100 ms | 4352 KB |
s3_35.txt | RE | 101 ms | 4352 KB |
s3_36.txt | RE | 99 ms | 4352 KB |
s3_37.txt | RE | 97 ms | 4352 KB |
s3_38.txt | RE | 102 ms | 4352 KB |
s3_39.txt | RE | 97 ms | 4352 KB |
s3_40.txt | WA | 3 ms | 4352 KB |
s3_41.txt | WA | 3 ms | 4352 KB |