| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 518654 |
2022-01-24T11:17:03 Z |
ac2hu |
Inspection (POI11_ins) |
C++14 |
|
557 ms |
131076 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 10;
vector<int> adj[N];
int n;
int mx[N], nodes[N], total_subtree[N], full_total[N], ans[N];
struct LCA{
int n,l,timer;
vector<int> tin, tout,dist;
vector<vector<int>> up;
LCA(int root,int siz){
n = siz; timer = 0; l = ceil(log2(n));
tin.resize(n); tout.resize(n); dist.resize(n,0); up.assign(n,vector<int>(l + 1));
dfs0(root,root);
}
void dfs0(int v, int p){
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i <= l; ++i){
up[v][i] = up[up[v][i-1]][i-1];
}
for (int u : adj[v]) {
if (u != p){
dist[u] = dist[v] + 1;
dfs0(u, v);
}
}
tout[v] = ++timer;
}
// Check if u is ancestor of v
bool is_ancestor(int u,int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
// Find LCA of u and v
int lcaquery(int u,int v){
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = l; i >= 0; --i) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
int distance(int u,int v){
int ll = lcaquery(u,v);
return dist[u] + dist[v] - 2*dist[ll];
}
};
void dfs(int i,int p){
for(auto e : adj[i]){
if(e == p)continue;
mx[e] = mx[i] + 1;
dfs(e,i);
}
}
void dfs1(int i,int p){
nodes[i] = 1;
total_subtree[i] = 0;
for(int e : adj[i]){
if(e == p)continue;
dfs1(e,i);
nodes[i] += nodes[e];
total_subtree[i] += total_subtree[e] + nodes[e];
}
}
void dfs2(int i,int p){
int mx = n - nodes[i];
for(int e : adj[i]){
if(e == p)continue;
full_total[e] = full_total[i] - nodes[e] + n - nodes[e];
dfs2(e,i);
mx = max(mx, nodes[e]);
}
if(mx >= n - mx)
ans[i] = -1;
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n;
for(int i = 0;i<n - 1;i++){
int a,b;cin >> a >> b;
a--;b--;
adj[a].push_back(b);
adj[b].push_back(a);
}
LCA lc(0,n + 1);
pair<int,int> dia;
dia.first = max_element(lc.dist.begin(),lc.dist.end()) - lc.dist.begin();
dfs(dia.first,-1);
dia.second = max_element(mx, mx + n) - mx;
for(int i =0;i<n;i++){
mx[i] = max(lc.distance(i,dia.first), lc.distance(i,dia.second));
}
dfs1(0,-1);
full_total[0] = total_subtree[0];
dfs2(0,-1);
// for(int i = 0;i<n;i++)
// cout << full_total[i] << " ";
// cout << "\n";
for(int i = 0;i<n;i++){
if(ans[i] != -1){
ans[i] = 2*full_total[i] - mx[i];
}
}
for(int i = 0;i<n;i++)
cout << ans[i] << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
23756 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
23808 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
12 ms |
24204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
34 ms |
29132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
49 ms |
34372 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
154 ms |
52172 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
335 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
557 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
556 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
522 ms |
131076 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
