Submission #938038

#	Time	Username	Problem	Language	Result	Execution time	Memory
938038		guechotjrhh	Unique Cities (JOI19_ho_t5)	C++14	0 / 100	115 ms	274432 KiB

joi2019_ho_t5

#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 30000000
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: 0 / 4
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32