Submission #486830

#TimeUsernameProblemLanguageResultExecution timeMemory
486830julian33Untitled (POI11_ins)C++14
0 / 100
1427 ms100124 KiB
#include <bits/stdc++.h> using namespace std; #ifdef LOCAL #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) { cerr<<vars<<" = "; string delim=""; (...,(cerr<<delim<<values,delim=", ")); cerr<<"\n"; } #else #define deb(...) logger(#__VA_ARGS__, __VA_ARGS__) template<typename ...Args> void logger(string vars, Args&&... values) {} #endif #define pb push_back #define sz(x) (int)(x.size()) typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; template<typename T> inline void maxa(T& a,T b){a=max(a,b);} template<typename T> inline void mina(T& a,T b){a=min(a,b);} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int mxN=1e6+5; //make sure this is right const int mod=1e9+7; vector<int> graph[mxN]; int sub[mxN],sub2[mxN],up[mxN],down[mxN],par[mxN],dp[mxN],dp2[mxN]; void dfs(int at,int p){ sub[at]=1; for(int &i:graph[at]){ if(i==p) continue; par[i]=at; dfs(i,at); sub[at]+=sub[i]; dp[at]+=dp[i]+sub[i]; maxa(down[at],down[i]+1); } } void dfs2(int at,int p){ vector<int> all; sub2[at]++; for(int &i:graph[at]){ if(i==p) continue; all.pb(down[i]); sub2[i]=sub[at]-1-sub[i]+sub2[at]; } sort(all.rbegin(),all.rend()); for(int &i:graph[at]){ if(i==p) continue; up[i]=up[at]+1; if(all[0]!=down[i]) maxa(up[i],all[0]+2); else if(sz(all)>1) maxa(up[i],all[1]+2); dp2[i]=dp2[at]+sub2[i]+dp[at]-sub[i]-dp[i]; dfs2(i,at); } } int main(){ cin.sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef LOCAL freopen("input.txt","r",stdin); freopen("output.txt","w",stdout); #endif int n; cin>>n; for(int i=1;i<n;i++){ int a,b; cin>>a>>b; graph[a].pb(b); graph[b].pb(a); } dfs(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++){ vector<int> all; int sum=0; for(int &j:graph[i]){ if(j==par[i]) continue; all.pb(sub[j]); sum+=sub[j]; } int rem=n-1-sum; sum+=rem; all.pb(rem); sort(all.begin(),all.end()); if(sum/2>sum-all.back()) cout<<-1<<"\n"; else cout<<2*(dp[i]+dp2[i])-max(up[i],down[i])<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...