답안 #937491

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
937491 2024-03-04T07:08:32 Z guechotjrhh Unique Cities (JOI19_ho_t5) C++14
0 / 100
326 ms 24544 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 + 1 > 0) {
		if (lev - mx2 - 1 >= 0) l = qu(1, lev - mx2 - 1, 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;*/

	return res;
}


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;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Incorrect 5 ms 3796 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 210 ms 18256 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 326 ms 24544 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3420 KB Output is correct
2 Incorrect 5 ms 3796 KB Output isn't correct
3 Halted 0 ms 0 KB -