Submission #936839

#	Time	Username	Problem	Language	Result	Execution time	Memory
936839		guechotjrhh	Unique Cities (JOI19_ho_t5)	C++14	32 / 100	575 ms	84252 KiB

joi2019_ho_t5

#include<iostream>
#include<vector>
using namespace std;



#include<iostream>
#include<vector>
#include<set>
using namespace std;
#define pi pair<int,int>
#define x first
#define y second
void dfs1(int i, int p, vector<vector<int>>& g, vector<multiset<pair<pi,int>>>& far) {
	far[i].insert({ { 0,0 },i });
	for (int j : g[i]) {
		if (j == p) continue;
		dfs1(j, i, g, far);
		pair<pi,int> p = *prev(far[j].end());
		if (far[j].size() > 1) {
			if (prev(prev(far[j].end()))->x.x >= p.x.y) p.x.y = 0;
		}
		p.x.y++;
		p.x.x++;
		p.y = j;
		far[i].insert(p);
	}
}
void dfs2(int i, int p, vector<vector<int>>& g, vector<multiset<pair<pi,int>>>&far, pi pr) {
	far[i].insert({ pr,-1 });

	for (int j : g[i]) {
		if (j == p) continue;

		pair<pi, int> pa;
		if (j == prev(far[i].end())->y) {
			pa = *prev(prev(far[i].end()));
			if (far[i].size() > 2) {
				if (prev(prev(prev(far[i].end())))->x.x >= pa.x.y) pa.x.y = 0;
			}
			pa.x.x++;
			pa.x.y++;
		}
		else {
			pa = *prev(far[i].end());

			if (j == prev(prev(far[i].end()))->y) {
				if (far[i].size()>2 && prev(prev(prev(far[i].end())))->x.x >= pa.x.y) pa.x.y = 0;
			}
			else {
				if (prev(prev(far[i].end()))->x.x >= pa.x.y) pa.x.y = 0;
			}
			pa.x.x++;
			pa.x.y++;
		}
		dfs2(j, i, g, far, pa.x);
	}
}

vector<int> find(int N, int M, vector<int> A, vector<int> B, vector<int> W) {
	vector<int> res(N, 0);
	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);
	}
	vector<multiset<pair<pi,int>>> far(N);
	dfs1(0, -1, g, far);
	//for (multiset<pair<pi,int>> s : far) {for (pair<pi,int> i : s) cout << i.x.x<<' '<<i.x.y << ' ' << i.y << '\t'; cout << endl; }
	dfs2(0, -1, g, far, { -1,-1 });
	//for (multiset<pair<pi, int>> s : far) { for (pair<pi, int> i : s) cout << i.x.x << ' ' << i.x.y << ' ' << i.y << '\t'; cout << endl; }


	for (int i = 0; i < N; i++) {
		pi p = prev(far[i].end())->x;
		if (far[i].size() > 1 && prev(prev(far[i].end()))->x.x >= p.y) p.y = 0;
		if (p.y) res[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;
}
/*

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

5 2
1 2
2 3
3 4
3 5
1 1 1 1 1

7 2
1 2
1 3
3 4
4 5
4 6
6 7
1 1 1 1 1 1 1

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