oj.uz

Submission #1011642

# Submission time Handle Problem Language Result Execution time Memory
1011642 2024-07-01T02:28:02 Z biximo Meetings 2 (JOI21_meetings2) C++17
0 / 100
 2 ms 10588 KB 
#include <bits/stdc++.h>
#define N 200005
#define INF 1000000000
using namespace std;
int n, sz[N], dpt[N], tb[N][18];
vector<int> adj[N];
bool vs[N];
void size_DFS(int c, int p) {
	sz[c] = 1;
	for(int i = 1; i < 18; i ++) {
		tb[c][i] = tb[tb[c][i-1]][i-1];
	}
	for(int i: adj[c]) {
		if(i == p) continue;
		dpt[i] = dpt[c]+1;
		tb[i][0] = c;
		size_DFS(i, c);
		sz[c] += sz[i];
	}
}
int jump(int a, int ds) {
	for(int i = 0; i < 18; i ++) {
		if(ds&1<<i) a = tb[a][i];
	}
	return a;
}
int LCA(int a, int b) {
	if(dpt[a] != dpt[b]) {
		if(dpt[a] < dpt[b]) swap(a,b);
		a = jump(a, dpt[a]-dpt[b]);
	}
	if(a == b) return a;
	for(int i = 17; i >= 0; i --) {
		if(tb[a][i] != tb[b][i]) {
			a = tb[a][i];
			b = tb[b][i];
		}
	}
	return tb[a][0];
}
int getSize(int c, int rt) {
	int lca = LCA(c,rt);
	if(lca != c) {
		return sz[c];
	} else {
		assert(dpt[rt] > dpt[c]);
		return sz[1]-sz[jump(rt,dpt[rt]-dpt[c]-1)];
	}
}
int sub_sz[N];
void size_2_DFS(int c, int p) {
	sub_sz[c] = 1;
	for(int i: adj[c]) {
		if(vs[i] || i == p) continue;
		size_2_DFS(i, c);
		sub_sz[c] += sub_sz[i];
	}
}
int find_cent_DFS(int c, int p, int tree_sz) {
	for(int i: adj[c]) {
		if(i == p || vs[i] || sub_sz[i]*2<tree_sz) continue;
		return find_cent_DFS(i, c, tree_sz);
	}
	return c;
}
struct Segtree {
	vector<int> tree;
	int len;
	void init(int n) {
		len = 1<<18;
		// len = 1;
		// while(len <= n) len *= 2;
		tree = vector<int>(len*2,-INF);
	}
	void update(int a, int v) {
		tree[a+len] = max(tree[a+len],v);
		for(a = (a+len)>>1; a >= 1; a >>= 1) {
			tree[a] = max(tree[a*2],tree[a*2+1]);
		}
	}
	void erase(int a) {
		tree[a+len] = -INF;
		for(a = (a+len)>>1; a >= 1; a >>= 1) {
			tree[a] = max(tree[a*2],tree[a*2+1]);
		}
	}
	int query(int a, int b) {
		int res = -INF;
		for(a += len, b += len; a <= b; a >>= 1, b >>= 1) {
			if(a&1) res = max(res, tree[a++]);
			if(~b&1) res = max(res, tree[b--]);
		}
		return res;
	}
	Segtree() {}
} tree;
int ans[N];
void ans_DFS(int c, int dt, int p, int rt) {
	for(int i: adj[c]) {
		if(vs[i] || i == p) continue;
		ans_DFS(i, dt+1, c, rt);
	}
	if(c == rt) return;
	int csz = getSize(c, rt);
	ans[csz] = max(ans[csz], dt+tree.query(csz,tree.len-1)+1);
	int rsz = getSize(rt, c);
	ans[min(rsz,csz)] = max(ans[min(rsz,csz)], dt+1);
}
void upd_DFS(int c, int dt, int p, int rt) {
	for(int i: adj[c]) {
		if(vs[i] || i == p) continue;
		upd_DFS(i, dt+1, c, rt);
	}
	if(c == rt) return;
	int csz = getSize(c, rt);
	tree.update(csz, dt);
}
void ers_DFS(int c, int dt, int p, int rt) {
	for(int i: adj[c]) {
		if(vs[i] || i == p) continue;
		ers_DFS(i, dt+1, c, rt);
	}
	if(c == rt) return;
	int csz = getSize(c, rt);
	tree.erase(csz);
}
void centroid_DFS(int c) {
	size_2_DFS(c, -1);
	int cent = find_cent_DFS(c, -1, sub_sz[c]);
	vs[cent] = 1;
	for(int i: adj[cent]) {
		if(vs[i]) continue;
		ans_DFS(i, 1, cent, cent);
		upd_DFS(i, 1, cent, cent);
	}
	for(int i: adj[cent]) {
		ers_DFS(i, 1, cent, cent);
	}
	for(int i: adj[cent]) {
		if(vs[i]) continue;
		centroid_DFS(i);
	}
}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> n;
    tree.init(n);
    for(int i = 1, u, v; i < n; i ++) {
    	cin >> u >> v;
    	adj[u].push_back(v);
    	adj[v].push_back(u);
    }
    size_DFS(1,-1);
    centroid_DFS(1);
    for(int i = n/2; i >= 1; i --) {
    	ans[i] = max({ans[i], ans[i+1], 1});
    }
    for(int i = 1; i <= n; i ++) {
    	if(i%2) cout << "1\n";
    	else cout << ans[i/2] << "\n";
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Incorrect 2 ms 10584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Incorrect 2 ms 10584 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 2 ms 10588 KB Output is correct
4 Correct 2 ms 10588 KB Output is correct
5 Correct 2 ms 10584 KB Output is correct
6 Incorrect 2 ms 10584 KB Output isn't correct
7 Halted 0 ms 0 KB -