oj.uz

Submission #937606

# Submission time Handle Problem Language Result Execution time Memory
937606 2024-03-04T09:35:50 Z guechotjrhh Unique Cities (JOI19_ho_t5) C++14
32 / 100
 455 ms 55120 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 3416 KB Output is correct
2 Incorrect 5 ms 3676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 18332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 24548 KB Output is correct
2 Correct 435 ms 52640 KB Output is correct
3 Correct 63 ms 9564 KB Output is correct
4 Correct 385 ms 30180 KB Output is correct
5 Correct 455 ms 55120 KB Output is correct
6 Correct 411 ms 42440 KB Output is correct
7 Correct 354 ms 30040 KB Output is correct
8 Correct 411 ms 34588 KB Output is correct
9 Correct 401 ms 33244 KB Output is correct
10 Correct 410 ms 31996 KB Output is correct
11 Correct 346 ms 30284 KB Output is correct
12 Correct 444 ms 49816 KB Output is correct
13 Correct 387 ms 40320 KB Output is correct
14 Correct 399 ms 40976 KB Output is correct
15 Correct 319 ms 30920 KB Output is correct
16 Correct 388 ms 47052 KB Output is correct
17 Correct 405 ms 42580 KB Output is correct

Subtask #4
0 / 32.0

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