oj.uz

Submission #938035

# Submission time Handle Problem Language Result Execution time Memory
938035 2024-03-04T18:26:56 Z guechotjrhh Unique Cities (JOI19_ho_t5) C++14
36 / 100
 875 ms 226480 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)
#define maxs (1<<18)
#define maxm 10000000
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));
}

int nxt = 0;
vector<int> vp(maxm,0), lp(maxm,-1), rp(maxm,-1);
void upp(int ind, int i, int l, int r) {
	int u = nxt; nxt++;
	if (ind != -1) vp[u] = vp[ind] + 1;
	else vp[u] = 1;

	//cout << ind << ' ' << u << ' ' << vp[u] << endl;

	if (l == r) return;

	int rs = ind == -1 ? -1 : rp[ind], ls = ind == -1 ? -1 : lp[ind];

	int m = (l + r) / 2;
	if (i > m) {
		upp(rs, i, m + 1, r);
		rp[u] = u + 1;
		lp[u] = ls;
	}
	else {
		upp(ls, i, l, m);
		lp[u] = u + 1;
		rp[u] = rs;
	}
}
int check(int ind, int i, int l, int r) {
	if (ind == -1) return 0;
	if (l == r) return vp[ind];
	int m = (l + r) / 2;
	if (i > m) return check(rp[ind], i, m + 1, r);
	else return check(lp[ind], i, l, m);
}
int sm(int ind) {
	if (ind == -1) return 0;
	return vp[ind];
}

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, vector<int>&indres, vector<int>&W) {
	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;
		if (check(indres[vert[l]], W[vert[l]], 0, maxs - 1)) {
			indres[i] = indres[vert[l]];
		}
		else {
			indres[i] = nxt;
			upp(indres[vert[l]], W[vert[l]], 0, maxs - 1);
		}
	}
	else indres[i] = indres[vert[0]];
	//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, indres,W);
	}

	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;
		if (check(indres[vert[l]], W[vert[l]], 0, maxs - 1)) {
			indres[i] = indres[vert[l]];
		}
		else {
			indres[i] = nxt;
			upp(indres[vert[l]], W[vert[l]], 0, maxs - 1);
		}
	}
	else indres[i] = indres[vert[0]];
	//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, indres,W);
	}
}
void dfs(int i, int p, int d, vector<vector<int>>& vec, vector<vector<int>>& g) {
	vec[d].push_back(i);
	for (int j : g[i]) {
		if (j != p) dfs(j, i, d + 1, vec, g);
	}
}
vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
	if (N <= 3) {
		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);
		}
		for (int i = 0; i < N; i++) {
			vector<vector<int>> vec(N);
			dfs(i, -1, 0, vec, g);
			set<int> st;
			for (int j = 1; j < N; j++) if (vec[j].size() == 1) st.insert(W[vec[j][0]]);
			res[i] = st.size();
		}

		return res;
	}
	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;
	//for (int i : row) cout << dep[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> indl(len, -1), indr(len, -1);
	//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;
			if (check(indl[le[i]], W[row[le[i]]], 0, maxs - 1)) {
				indl[i] = indl[le[i]];
			}
			else {
				indl[i] = nxt;
				upp(indl[le[i]], W[row[le[i]]], 0, maxs - 1);
			}
		}
	}
	for (int i = len-1; i >= 0; i--) {
		//if (ri[i] <  len) cntr[i] = cntr[ri[i]] + 1;
		if (ri[i] >= len) continue;
		if (check(indr[ri[i]], W[row[ri[i]]], 0, maxs - 1)) {
			indr[i] = indr[ri[i]];
		}
		else {
			indr[i] = nxt;
			upp(indr[ri[i]], W[row[ri[i]]], 0, maxs - 1);
		}
	}
	//cout<<"count:\n";
	//for (int i = 0; i < len; i++) cout << i << ' ' << cntl[i] << ' ' << cntr[i] << endl;

	//for (int i : indr) cout << i << ' '; cout << endl;
	//for (int i : indl) cout << i << ' '; cout << endl;

	int lm = len / 2 - 1, rm = (len + 1) / 2;
	
	vector<int> indres(N, -1);
	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;
			if (check(indr[cto], W[row[cto]], 0, maxs - 1)) {
				//cout << i << 'A';
				indres[row[i]] = indr[cto];
			}
			else {
				//cout << i << 'B';
				indres[row[i]] = nxt;
				upp(indr[cto], W[row[cto]], 0, maxs - 1);
			}
		}
		//else res[row[i]] = 0;
	}//cout << endl;
	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;
			if (check(indl[cto], W[row[cto]], 0, maxs - 1)) {
				indres[row[i]] = indl[cto];
			}
			else {
				indres[row[i]] = nxt;
				upp(indl[cto], W[row[cto]], 0, maxs - 1);
			}
		}
		//else res[row[i]] = 0;
	}
	//if (len & 1) res[row[len / 2]] = 0;
	//for (int i : row) cout << i << ' ' << indres[i] << endl;

	vector<int> vert(N), add(N, 0);
	for (int i = 1; i < len - 1; i++) {
		dfs3(row[i], -1, g, dep, 0, vert, add, indres,W);
	}
	for (int i = 0; i < N; i++) {
		//if (res[i] == -1) res[i] = res[row[par[i]]] + add[i];
		res[i] = sm(indres[i]);
	}
	//persistent seg tree for 100!
	/*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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 120752 KB Output is correct
2 Correct 37 ms 121104 KB Output is correct
3 Correct 27 ms 121168 KB Output is correct
4 Correct 28 ms 121168 KB Output is correct
5 Correct 29 ms 121180 KB Output is correct
6 Correct 28 ms 121236 KB Output is correct
7 Correct 28 ms 121172 KB Output is correct
8 Correct 31 ms 121140 KB Output is correct
9 Correct 29 ms 121176 KB Output is correct
10 Correct 31 ms 121244 KB Output is correct
11 Correct 29 ms 121168 KB Output is correct
12 Correct 28 ms 121420 KB Output is correct
13 Correct 36 ms 121424 KB Output is correct
14 Correct 28 ms 121176 KB Output is correct
15 Correct 28 ms 121172 KB Output is correct
16 Correct 27 ms 121336 KB Output is correct
17 Correct 29 ms 121184 KB Output is correct
18 Correct 28 ms 121268 KB Output is correct
19 Correct 29 ms 121176 KB Output is correct
20 Correct 30 ms 121472 KB Output is correct
21 Correct 29 ms 121172 KB Output is correct
22 Correct 29 ms 121172 KB Output is correct
23 Correct 30 ms 121240 KB Output is correct
24 Correct 29 ms 121180 KB Output is correct
25 Correct 28 ms 121252 KB Output is correct
26 Correct 28 ms 121176 KB Output is correct
27 Correct 31 ms 121168 KB Output is correct
28 Correct 32 ms 121368 KB Output is correct
29 Correct 30 ms 121216 KB Output is correct
30 Correct 30 ms 120964 KB Output is correct
31 Correct 29 ms 121156 KB Output is correct
32 Correct 29 ms 121180 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 135156 KB Output is correct
2 Correct 259 ms 150516 KB Output is correct
3 Correct 79 ms 126288 KB Output is correct
4 Correct 406 ms 145744 KB Output is correct
5 Correct 458 ms 172500 KB Output is correct
6 Correct 459 ms 158804 KB Output is correct
7 Correct 410 ms 145872 KB Output is correct
8 Correct 425 ms 148564 KB Output is correct
9 Correct 409 ms 147540 KB Output is correct
10 Correct 410 ms 147536 KB Output is correct
11 Correct 377 ms 146888 KB Output is correct
12 Correct 434 ms 162192 KB Output is correct
13 Correct 409 ms 158668 KB Output is correct
14 Correct 449 ms 158088 KB Output is correct
15 Correct 367 ms 146452 KB Output is correct
16 Correct 434 ms 163664 KB Output is correct
17 Correct 445 ms 159184 KB Output is correct

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 360 ms 141140 KB Output is correct
2 Runtime error 875 ms 226480 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 120752 KB Output is correct
2 Correct 37 ms 121104 KB Output is correct
3 Correct 27 ms 121168 KB Output is correct
4 Correct 28 ms 121168 KB Output is correct
5 Correct 29 ms 121180 KB Output is correct
6 Correct 28 ms 121236 KB Output is correct
7 Correct 28 ms 121172 KB Output is correct
8 Correct 31 ms 121140 KB Output is correct
9 Correct 29 ms 121176 KB Output is correct
10 Correct 31 ms 121244 KB Output is correct
11 Correct 29 ms 121168 KB Output is correct
12 Correct 28 ms 121420 KB Output is correct
13 Correct 36 ms 121424 KB Output is correct
14 Correct 28 ms 121176 KB Output is correct
15 Correct 28 ms 121172 KB Output is correct
16 Correct 27 ms 121336 KB Output is correct
17 Correct 29 ms 121184 KB Output is correct
18 Correct 28 ms 121268 KB Output is correct
19 Correct 29 ms 121176 KB Output is correct
20 Correct 30 ms 121472 KB Output is correct
21 Correct 29 ms 121172 KB Output is correct
22 Correct 29 ms 121172 KB Output is correct
23 Correct 30 ms 121240 KB Output is correct
24 Correct 29 ms 121180 KB Output is correct
25 Correct 28 ms 121252 KB Output is correct
26 Correct 28 ms 121176 KB Output is correct
27 Correct 31 ms 121168 KB Output is correct
28 Correct 32 ms 121368 KB Output is correct
29 Correct 30 ms 121216 KB Output is correct
30 Correct 30 ms 120964 KB Output is correct
31 Correct 29 ms 121156 KB Output is correct
32 Correct 29 ms 121180 KB Output is correct
33 Correct 235 ms 135156 KB Output is correct
34 Correct 259 ms 150516 KB Output is correct
35 Correct 79 ms 126288 KB Output is correct
36 Correct 406 ms 145744 KB Output is correct
37 Correct 458 ms 172500 KB Output is correct
38 Correct 459 ms 158804 KB Output is correct
39 Correct 410 ms 145872 KB Output is correct
40 Correct 425 ms 148564 KB Output is correct
41 Correct 409 ms 147540 KB Output is correct
42 Correct 410 ms 147536 KB Output is correct
43 Correct 377 ms 146888 KB Output is correct
44 Correct 434 ms 162192 KB Output is correct
45 Correct 409 ms 158668 KB Output is correct
46 Correct 449 ms 158088 KB Output is correct
47 Correct 367 ms 146452 KB Output is correct
48 Correct 434 ms 163664 KB Output is correct
49 Correct 445 ms 159184 KB Output is correct
50 Correct 360 ms 141140 KB Output is correct
51 Runtime error 875 ms 226480 KB Execution killed with signal 6
52 Halted 0 ms 0 KB -