Submission #168359

#TimeUsernameProblemLanguageResultExecution timeMemory
168359ThuleanxUntitled (POI11_ins)C++14
70 / 100
1713 ms131076 KiB
#include <bits/stdc++.h> using namespace std; const int N = 1e6; int n; int sz[N]; vector<int> adj[N]; long long ans[N]; long long rans[N]; long long dans[N]; int lp[N]; bool valid[N]; int dfs(int v, int p) { sz[v] = 1; ans[v] = 0; lp[v] = 0; for (int w : adj[v]) if (w != p) { sz[v] += dfs(w,v); ans[v] += ans[w] + sz[w]; lp[v] = max(lp[v], lp[w]+1); } return sz[v]; } void dfsr(int v, int p, int len) { rans[v] = v ? rans[p] + (n - sz[v]) - sz[v] : ans[v]; vector<int> xp; xp.push_back(len+1); int max_sz = 0, llen = 0; for (int w : adj[v]) if (w != p) { if (sz[w] > max_sz) { max_sz = sz[w]; llen = lp[w]+1; } xp.push_back(lp[w]+2); sort(begin(xp),end(xp),greater<int>()); while (xp.size() > 2) xp.pop_back(); } if (n-sz[v] > max_sz) { max_sz = n-sz[v]; llen = len; } valid[v] = max_sz - (n - 1 - max_sz) <= 1; dans[v] = max(len, lp[v]); if (max_sz - (n - 1 - max_sz) == 1) dans[v] = llen; for (int w : adj[v]) if (w != p) { int l = xp[0]; if (xp[0] == lp[w]+2) l = xp[1]; dfsr(w,v,l); } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin>>n; for (int i = 0; i < n-1; i++) { int a, b; cin>>a>>b; adj[--a].push_back(--b); adj[b].push_back(a); } dfs(0,-1); dfsr(0,-1, 0); stringstream ss; for (int i = 0; i < n; i++) ss << (valid[i] ? 2*rans[i]-dans[i] : -1) << endl; cout << ss.str(); return 0; }
#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...