oj.uz

Submission #937608

# Submission time Handle Problem Language Result Execution time Memory
937608 2024-03-04T09:36:30 Z guechotjrhh Unique Cities (JOI19_ho_t5) C++14
64 / 100
 592 ms 54100 KB 
#include<iostream>
#include<vector>
using namespace std;



#include<iostream>
#include<vector>
#include<set>
#include<stack>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
#define maxn (1<<17)

vector<int> v(2 * maxn, 1e9), l(2 * maxn), r(2 * maxn);
void bld() {
	for (int i = maxn; i < 2 * maxn; i++) {
		l[i] = r[i] = i - maxn;
	}
	for (int i = maxn - 1; i > 0; i--) {
		l[i] = l[2 * i];
		r[i] = r[2 * i + 1];
	}
}
void up(int i, int u) {
	i += maxn;
	v[i] = u;
	while (i >>= 1) v[i] = min(v[i << 1], v[(i << 1) + 1]);
}
int qu(int i, int s, int e) {
	if (l[i] > e || r[i] < s) return 1e9;
	if (l[i] >= s && r[i] <= e) return v[i];
	return min(qu(i << 1, s, e), qu((i << 1) + 1, s, e));
}

pi dfs0(int i, int p, vector<vector<int>>& g) {
	pi pr = { 0,i };
	for (int j : g[i]) {
		if (j == p) continue;
		pi r = dfs0(j, i, g);
		r.x++;
		if (r > pr) pr = r;
	}
	return pr;
}
bool dfs1(int i, int p, vector<vector<int>>& g, int d, vector<int>&dep, vector<int>&row, int x) {
	bool flag = 0;
	if (i == x) flag = 1;
	dep[i] = 0;
	for (int j : g[i]) {
		if (j == p) continue;
		if (dfs1(j, i, g, d + 1, dep, row, x)) flag = 1;
		else dep[i] = max(dep[i], dep[j] + 1);
	}
	if (flag) row[d] = i;
	return flag;
}
void dfs2(int i, int p, vector<vector<int>>& g, vector<int>&par, int f) {
	par[i] = f;
	for (int j : g[i]) {
		if (j == p) continue;
		dfs2(j, i, g, par, f);
	}
}
void dfs3(int i, int p, vector<vector<int>>& g, vector<int>&dep, int lev, vector<int> &vert, vector<int>&add) {
	int mx1 = -1, mx2 =-1;
	for (int j : g[i]) {
		if (j == p) continue;
		if (dep[j]+1 > mx1) {
			mx2 = mx1;
			mx1 = dep[j]+1;
		}
		else if (dep[j]+1 > mx2) mx2 = dep[j]+1;
	}
	vert[lev] = i;
	

	int l = lev - 1;
	if (mx2 > 0) {
		if (lev - mx2 >= 0) l = qu(1, lev - mx2, lev - 1);
		else l = -1;
	}
	if (l > -1) add[i] = add[vert[l]] + 1;
	else add[i] = 0;
	up(lev, l);
	for (int j : g[i]) {
		if (j == p) continue;
		if (dep[j] + 1 == mx1) dfs3(j, i, g, dep, lev + 1, vert, add);
	}

	l = lev - 1;
	if (dep[i] > 0) {
		if (lev - dep[i] >= 0) l = qu(1, lev - dep[i], lev - 1);
		else l = -1;
	}
	if (l > -1) add[i] = add[vert[l]] + 1;
	else add[i] = 0;
	up(lev, l);

	for (int j : g[i]) {
		if (j == p) continue;
		if (dep[j] + 1 == mx1) continue;
		dfs3(j, i, g, dep, lev + 1, vert, add);
	}
}

vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
	bld();
	vector<int> res(N, -1);
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; i++) {
		g[A[i] - 1].push_back(B[i] - 1);
		g[B[i] - 1].push_back(A[i] - 1);
	}
	int rt = dfs0(0, -1, g).y;
	pi pr = dfs0(rt, -1, g);
	int ort = pr.y, len = pr.x + 1;
	vector<int> dep(N, 0), row(len, -1);
	dfs1(rt, -1, g, 0, dep, row, ort);
	//for (int i : dep) cout << i << ' '; cout << endl;
	//for (int i : row) cout << i << ' '; cout << endl;
	vector<int> par(N, -1);
	for (int i = 1; i < len - 1; i++) {
		for (int& j : g[row[i]]) if (j == row[i - 1] || j == row[i + 1]) j = -1;
		dfs2(row[i], -1, g, par, i);
	}
	//for (int i : par) cout << i << ' '; cout << endl;
	
	vector<int> le(len, -1), ri(len, len);
	stack<int> sk;
	//monotonic stack
	for (int i = 0; i < len; i++) {
		int u = row[i];

		int to = i - dep[u];
		while (sk.size() && to <= sk.top()) {
			if (le[sk.top()]+1 < to) to = le[sk.top()]+1;
			sk.pop();
		}
		le[i] = (to >= 0) ? to - 1 : -1;

		sk.push(i);
	}
	for (int i = len - 1; i >= 0; i--) {
		int u = row[i];

		int to = i + dep[u];
		while (sk.size() && to >= sk.top()) {
			if (ri[sk.top()]-1 > to) to = ri[sk.top()]-1;
			sk.pop();
		}
		ri[i] = to < len ? to + 1 : len;

		sk.push(i);
	}
	//for (int i = 0; i < len; i++) cout << i << ' ' << le[i] << ' ' << ri[i] << endl;

	vector<int> cntl(N, 0), cntr(N, 0);
	for (int i = 0; i < len; i++) {
		if (le[i] > -1) cntl[i] = cntl[le[i]] + 1;
	}
	for (int i = len-1; i >= 0; i--) {
		if (ri[i] <  len) cntr[i] = cntr[ri[i]] + 1;
	}
	//cout<<"count:\n";
	//for (int i = 0; i < len; i++) cout << i << ' ' << cntl[i] << ' ' << cntr[i] << endl;

	int lm = len / 2 - 1, rm = (len + 1) / 2;
	
	vector<int> rcl(N, 0), rcr(N, 0);
	int rto = -1, cto = -1;
	for (int i = 0; i <= lm; i++) {
		cto = max(cto, 2*i + 1);
		while (rto < cto - 1) {
			rto++;
			if (rto + dep[row[rto]] + 1 > cto) cto = rto + dep[row[rto]] + 1;
			if (cto > len) cto = len;
		}
		if (cto < len) res[row[i]] = cntr[cto] + 1;
		else res[row[i]] = 0;
	}
	int lto = len;
	cto = len;
	for (int i = len-1; i >= rm; i--) {
		cto = min(cto, 2*i - len);
		while (lto > cto + 1) {
			lto--;
			if (lto - dep[row[lto]] - 1 < cto) cto = lto - dep[row[lto]] - 1;
			if (cto < 0) cto = -1;
		}
		if (cto >= 0) res[row[i]] = cntl[cto] + 1;
		else res[row[i]] = 0;
	}
	if (len & 1) res[row[len / 2]] = 0;

	vector<int> vert(N), add(N, 0);
	for (int i = 1; i < len - 1; i++) {
		dfs3(row[i], -1, g, dep, 0, vert, add);
	}
	for (int i = 0; i < N; i++) {
		if (res[i] == -1) res[i] = res[row[par[i]]] + add[i];
	}

	/*vector<int> am(len), ap(len);
	vector<vector<int>> vp(18, vector<int>(len, 1e9)), vm(18, vector<int>(len, 1e9));
	for (int i = 0; i < len; i++) {
		am[i] = i - dep[i];
		ap[i] = i + dep[i];
		vm[0][i] = am[i];
		vp[0][i] = ap[i];
	}
	for (int j = 1; j < 18; j++) {
		for (int i = 0; i < len; i++) {
			vp[j][i] = vp[j - 1][i];
			vm[j][i] = vm[j - 1][i];
		}
		for (int i = 0; i + (1 << (j - 1)) < len; i++) {
			vp[j][i] = min(vp[j - 1][i], vp[j - 1][i + (1 << (j - 1))]);
			vm[j][i] = min(vm[j - 1][i], vm[j - 1][i + (1 << (j - 1))]);
		}
	}
	vector<int> lg(len+1, 0);
	lg[1] = 0;
	for (int i = 2; i <= len; i++) lg[i] = lg[i / 2] + 1;*/
	
	if (W[0] == W[1]) for (int &i : res) if (i > 1) i = 1;

	return res;
}

/*

15 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
5 10
10 11
10 14
11 12 
11 13
13 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

*/

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin >> N >> M;
	vector<int> A(N - 1), B(N - 1);
	for (int i = 0; i < N - 1; i++) {
		cin >> A[i] >> B[i];
	}
	vector<int> W(N);
	for (int i = 0; i < N; i++) {
		cin >> W[i];
	}

	vector<int> ans = find(N, M, A, B, W);

	for (int i = 0; i < N; i++) {
		cout << ans[i] << endl;
	}

	return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Incorrect 5 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 286 ms 16880 KB Output is correct
2 Correct 328 ms 32632 KB Output is correct
3 Correct 50 ms 8792 KB Output is correct
4 Correct 451 ms 29428 KB Output is correct
5 Correct 449 ms 54100 KB Output is correct
6 Correct 431 ms 41556 KB Output is correct
7 Correct 382 ms 29224 KB Output is correct
8 Correct 449 ms 31772 KB Output is correct
9 Correct 375 ms 30988 KB Output is correct
10 Correct 429 ms 30896 KB Output is correct
11 Correct 321 ms 29896 KB Output is correct
12 Correct 442 ms 44640 KB Output is correct
13 Correct 489 ms 41196 KB Output is correct
14 Correct 438 ms 40636 KB Output is correct
15 Correct 313 ms 29644 KB Output is correct
16 Correct 388 ms 46088 KB Output is correct
17 Correct 406 ms 41676 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 23416 KB Output is correct
2 Correct 511 ms 51208 KB Output is correct
3 Correct 59 ms 9564 KB Output is correct
4 Correct 460 ms 28472 KB Output is correct
5 Correct 526 ms 53328 KB Output is correct
6 Correct 592 ms 40932 KB Output is correct
7 Correct 388 ms 28496 KB Output is correct
8 Correct 473 ms 32848 KB Output is correct
9 Correct 394 ms 31420 KB Output is correct
10 Correct 436 ms 30056 KB Output is correct
11 Correct 352 ms 28528 KB Output is correct
12 Correct 420 ms 47956 KB Output is correct
13 Correct 375 ms 38604 KB Output is correct
14 Correct 508 ms 39108 KB Output is correct
15 Correct 319 ms 29124 KB Output is correct
16 Correct 451 ms 45296 KB Output is correct
17 Correct 443 ms 40652 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Incorrect 5 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -