Submission #1872916
Source Code Expand
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; struct edge { int to; ll cost; }; vector<int> G[MAX_N]; vector<edge> graph[MAX_N]; int par[MAX_N]; int st[MAX_N]; ll sma; void dfs(int u,int p) { par[u] = p; st[u] = 1; rep(i,len(G[u])){ if(G[u][i] != p){ dfs(G[u][i],u); st[u] += st[G[u][i]]; } } } void redfs(int u,int p,ll dist) { sma += dist; rep(i,len(graph[u])){ if(graph[u][i].to != p){ redfs(graph[u][i].to,u,dist+graph[u][i].cost); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vp vec(n-1); rep(i,n-1){ int a,b; cin >> a >> b; --a,--b; vec[i] = P(a,b); G[a].pb(b),G[b].pb(a); } vl sm(n); rep(i,n){ cin >> sm[i]; } dfs(0,-1); vl ans(n-1); int flag = -1; bool hoge = false; rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; bool cri = false; if(par[a] != b){ cri = true; swap(a,b); } if(n == 2*st[a]){ hoge = true; flag = i; continue; } ans[i] = (sm[a]-sm[b])/(n-2*st[a]); } if(flag >= 0){ rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; if(flag == i){ graph[a].pb((edge){b,0}),graph[b].pb((edge){a,0}); }else{ graph[a].pb((edge){b,ans[i]}),graph[b].pb((edge){a,ans[i]}); } } sma = 0; if(hoge){ redfs(vec[flag].fi,-1,0); ans[flag] = (sm[vec[flag].fi]-sma) / st[vec[flag].se]; }else{ redfs(vec[flag].se,-1,0); ans[flag] = (sm[vec[flag].se]-sma) / st[vec[flag].fi]; } } rep(i,n-1){ cout << ans[i] << "\n"; } return 0; } #include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; struct edge { int to; ll cost; }; vector<int> G[MAX_N]; vector<edge> graph[MAX_N]; int par[MAX_N]; int st[MAX_N]; ll sma; void dfs(int u,int p) { par[u] = p; st[u] = 1; rep(i,len(G[u])){ if(G[u][i] != p){ dfs(G[u][i],u); st[u] += st[G[u][i]]; } } } void redfs(int u,int p,ll dist) { sma += dist; rep(i,len(graph[u])){ if(graph[u][i].to != p){ redfs(graph[u][i].to,u,dist+graph[u][i].cost); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vp vec(n-1); rep(i,n-1){ int a,b; cin >> a >> b; --a,--b; vec[i] = P(a,b); G[a].pb(b),G[b].pb(a); } vl sm(n); rep(i,n){ cin >> sm[i]; } dfs(0,-1); vl ans(n-1); int flag = -1; bool hoge = false; rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; bool cri = false; if(par[a] != b){ cri = true; swap(a,b); } if(n == 2*st[a]){ hoge = true; flag = i; continue; } ans[i] = (sm[a]-sm[b])/(n-2*st[a]); } if(flag >= 0){ rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; if(flag == i){ graph[a].pb((edge){b,0}),graph[b].pb((edge){a,0}); }else{ graph[a].pb((edge){b,ans[i]}),graph[b].pb((edge){a,ans[i]}); } } sma = 0; if(hoge){ redfs(vec[flag].fi,-1,0); ans[flag] = (sm[vec[flag].fi]-sma) / st[vec[flag].se]; }else{ redfs(vec[flag].se,-1,0); ans[flag] = (sm[vec[flag].se]-sma) / st[vec[flag].fi]; } } rep(i,n-1){ cout << ans[i] << "\n"; } return 0; } #include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; struct edge { int to; ll cost; }; vector<int> G[MAX_N]; vector<edge> graph[MAX_N]; int par[MAX_N]; int st[MAX_N]; ll sma; void dfs(int u,int p) { par[u] = p; st[u] = 1; rep(i,len(G[u])){ if(G[u][i] != p){ dfs(G[u][i],u); st[u] += st[G[u][i]]; } } } void redfs(int u,int p,ll dist) { sma += dist; rep(i,len(graph[u])){ if(graph[u][i].to != p){ redfs(graph[u][i].to,u,dist+graph[u][i].cost); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vp vec(n-1); rep(i,n-1){ int a,b; cin >> a >> b; --a,--b; vec[i] = P(a,b); G[a].pb(b),G[b].pb(a); } vl sm(n); rep(i,n){ cin >> sm[i]; } dfs(0,-1); vl ans(n-1); int flag = -1; bool hoge = false; rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; bool cri = false; if(par[a] != b){ cri = true; swap(a,b); } if(n == 2*st[a]){ hoge = true; flag = i; continue; } ans[i] = (sm[a]-sm[b])/(n-2*st[a]); } if(flag >= 0){ rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; if(flag == i){ graph[a].pb((edge){b,0}),graph[b].pb((edge){a,0}); }else{ graph[a].pb((edge){b,ans[i]}),graph[b].pb((edge){a,ans[i]}); } } sma = 0; if(hoge){ redfs(vec[flag].fi,-1,0); ans[flag] = (sm[vec[flag].fi]-sma) / st[vec[flag].se]; }else{ redfs(vec[flag].se,-1,0); ans[flag] = (sm[vec[flag].se]-sma) / st[vec[flag].fi]; } } rep(i,n-1){ cout << ans[i] << "\n"; } return 0; } #include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)(n);++i) #define rrep(i,n) for(int i=(int)(n)-1;i>=0;--i) #define srep(i,s,t) for(int i=(int)(s);i<(int)(t);++i) #define each(a,b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define len(v) (int)(v).size() #define zip(v) sort(all(v)),v.erase(unique(all(v)),v.end()) #define cmx(x,y) x=max(x,y) #define cmn(x,y) x=min(x,y) #define fi first #define se second #define pb push_back #define show(x) cout<<#x<<" = "<<(x)<<endl #define spair(p) cout<<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout<<" "<<kbrni;cout<<endl #define smap(m) cout<<#m<<":";each(kbrni,m)cout<<" {"<<kbrni.first<<":"<<kbrni.second<<"}";cout<<endl using namespace std; typedef pair<int,int> P; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<ll> vl; typedef vector<vl> vvl; typedef vector<double> vd; typedef vector<P> vp; typedef vector<string> vs; const int MAX_N = 100005; struct edge { int to; ll cost; }; vector<int> G[MAX_N]; vector<edge> graph[MAX_N]; int par[MAX_N]; int st[MAX_N]; ll sma; void dfs(int u,int p) { par[u] = p; st[u] = 1; rep(i,len(G[u])){ if(G[u][i] != p){ dfs(G[u][i],u); st[u] += st[G[u][i]]; } } } void redfs(int u,int p,ll dist) { sma += dist; rep(i,len(graph[u])){ if(graph[u][i].to != p){ redfs(graph[u][i].to,u,dist+graph[u][i].cost); } } } int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; vp vec(n-1); rep(i,n-1){ int a,b; cin >> a >> b; --a,--b; vec[i] = P(a,b); G[a].pb(b),G[b].pb(a); } vl sm(n); rep(i,n){ cin >> sm[i]; } dfs(0,-1); vl ans(n-1); int flag = -1; bool hoge = false; rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; bool cri = false; if(par[a] != b){ cri = true; swap(a,b); } if(n == 2*st[a]){ hoge = true; flag = i; continue; } ans[i] = (sm[a]-sm[b])/(n-2*st[a]); } if(flag >= 0){ rep(i,n-1){ int a = vec[i].fi,b = vec[i].se; if(flag == i){ graph[a].pb((edge){b,0}),graph[b].pb((edge){a,0}); }else{ graph[a].pb((edge){b,ans[i]}),graph[b].pb((edge){a,ans[i]}); } } sma = 0; if(hoge){ redfs(vec[flag].fi,-1,0); ans[flag] = (sm[vec[flag].fi]-sma) / st[vec[flag].se]; }else{ redfs(vec[flag].se,-1,0); ans[flag] = (sm[vec[flag].se]-sma) / st[vec[flag].fi]; } } rep(i,n-1){ cout << ans[i] << "\n"; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | D - Ancient Tree Record |
User | kopricky |
Language | C++14 (GCC 5.4.1) |
Score | 0 |
Code Size | 12504 Byte |
Status | CE |
Compile Error
./Main.cpp:166:11: error: redefinition of ‘const int MAX_N’ const int MAX_N = 100005; ^ ./Main.cpp:36:11: note: ‘const int MAX_N’ previously defined here const int MAX_N = 100005; ^ ./Main.cpp:168:8: error: redefinition of ‘struct edge’ struct edge ^ ./Main.cpp:38:8: error: previous definition of ‘struct edge’ struct edge ^ ./Main.cpp:174:20: error: redefinition of ‘std::vector<int> G [100005]’ vector<int> G[MAX_N]; ^ ./Main.cpp:44:13: note: ‘std::vector<int> G [100005]’ previously declared here vector<int> G[MAX_N]; ^ ./Main.cpp:175:25: error: redefinition of ‘std::vector<edge> graph [100005]’ vector<edge> graph[MAX_N]; ^ ./Main.cpp:45:14: note: ‘std::vector<edge> graph [100005]’ previously declared here vector<edge> graph[MAX_N]; ^ ./Main.cpp:176:14: error: redefinition of ‘int par [100005]’ int par[MAX_N]; ^ ./Main.cpp:46:5: note: ‘int par [100005]’ previously declar...