oj.uz

Submission #936839

# Submission time Handle Problem Language Result Execution time Memory
936839 2024-03-02T19:43:59 Z guechotjrhh Unique Cities (JOI19_ho_t5) C++14
32 / 100
 575 ms 84252 KB 
#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.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 37088 KB Output is correct
2 Correct 278 ms 51264 KB Output is correct
3 Correct 51 ms 11352 KB Output is correct
4 Correct 575 ms 67032 KB Output is correct
5 Correct 516 ms 81244 KB Output is correct
6 Correct 529 ms 79188 KB Output is correct
7 Correct 533 ms 66964 KB Output is correct
8 Correct 512 ms 69200 KB Output is correct
9 Correct 494 ms 68448 KB Output is correct
10 Correct 549 ms 68580 KB Output is correct
11 Correct 536 ms 67628 KB Output is correct
12 Correct 544 ms 84252 KB Output is correct
13 Correct 546 ms 74444 KB Output is correct
14 Correct 521 ms 76492 KB Output is correct
15 Correct 521 ms 67372 KB Output is correct
16 Correct 537 ms 76484 KB Output is correct
17 Correct 539 ms 75984 KB Output is correct

Subtask #3
0 / 32.0

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

Subtask #4
0 / 32.0

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