Submission #3386450
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 | D - Ancient Tree Record |
User | leign |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 3114 Byte |
Status | CE |
Compile Error
./Main.cpp: In function ‘void Calc()’: ./Main.cpp:39:37: error: converting to ‘std::vector<std::tuple<int, long long int, int, int> >::value_type {aka std::tuple<int, long long int, int, int>}’ from initializer list would use explicit constructor ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int, int&, long unsigned int}; <template-parameter-2-2> = void; _Elements = {int, long long int, int, int}]’ G[a].push_back({b,0,i,G[b].size()}); ^ ./Main.cpp:40:39: error: converting to ‘std::vector<std::tuple<int, long long int, int, int> >::value_type {aka std::tuple<int, long long int, int, int>}’ from initializer list would use explicit constructor ‘constexpr std::tuple< <template-parameter-1-1> >::tuple(_UElements&& ...) [with _UElements = {int&, int, int&, long unsigned int}; <template-parameter-2-2> = void; _Elements = {int, long long int, int, int}]’ G[b].push_back({a,0,i,G[a].size()-1}); ...