oj.uz

답안 #534801

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
534801 2022-03-09T02:19:11 Z rk42745417 Unique Cities (JOI19_ho_t5) C++17
100 / 100
 379 ms 39936 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << "\e[1;31m" << #x << " = " << (x) << "\e[0m\n"
#define print(x) emilia_mata_tenshi(#x, begin(x), end(x))
template<typename T> void emilia_mata_tenshi(const char *s, T l, T r) {
	cerr << "\e[1;33m" << s << " = [";
	while(l != r) {
		cerr << *l;
		cerr << (++l == r ? ']' : ',');
	}
	cerr << "\e[0m\n";
}

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
static int Lamy_is_cute = []() {
	EmiliaMyWife
	return 48763;
}();
/*--------------------------------------------------------------------------------------*/

const int N = 2e5 + 25;
vector<int> edge[N];
int max_dep[N], ans[N], arr[N], dep[N];
pair<int, int> cal_dia(int u, int p) {
	pair<int, int> res = {0, u};
	for(int v : edge[u]) {
		if(v == p)
			continue;
		auto r = cal_dia(v, u);
		r.first++;
		res = max(res, r);
	}
	return res;
}
void cal_maxdep(int u, int p) {
	max_dep[u] = 0;
	for(int v : edge[u]) {
		if(v == p)
			continue;
		dep[v] = dep[u] + 1;
		cal_maxdep(v, u);
		max_dep[u] = max(max_dep[u], max_dep[v] + 1);
	}
}

int cnt[N], res = 0;
stack<int, vector<int>> cur;
void add(int x) {
	cur.push(x);
	if(cnt[arr[x]] == 0)
		res++;
	cnt[arr[x]]++;
}
void rem() {
	cnt[arr[cur.top()]]--;
	if(cnt[arr[cur.top()]] == 0)
		res--;
	cur.pop();
}
void cal_ans(int u, int p) {
	int mx = 0, smx = 0;
	for(int v : edge[u]) {
		if(v == p)
			continue;
		if(max_dep[v] + 1 > mx)
			swap(mx, smx), mx = max_dep[v] + 1;
		else
			smx = max(smx, max_dep[v] + 1);
	}

	for(int v : edge[u]) {
		if(v == p || max_dep[v] + 1 != mx)
			continue;
		while(!cur.empty() && dep[cur.top()] >= dep[u] - smx)
			rem();
		add(u);
		cal_ans(v, u);
	}

	for(int v : edge[u]) {
		if(v == p || max_dep[v] + 1 == mx)
			continue;
		while(!cur.empty() && dep[cur.top()] >= dep[u] - mx)
			rem();
		add(u);
		cal_ans(v, u);
	}

	while(!cur.empty() && dep[cur.top()] >= dep[u] - max_dep[u])
		rem();
	ans[u] = max(ans[u], res);
}

signed main() {
	int n, m;
	cin >> n >> m;
	for(int i = 1, u, v; i < n; i++) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	for(int i = 1; i <= n; i++)
		cin >> arr[i];

	auto [_, d1] = cal_dia(1, 1);
	auto [__, d2] = cal_dia(d1, d1);
	for(int d : {d1, d2}) {
		dep[d] = 0;
		cal_maxdep(d, d);
		cal_ans(d, d);
	}

	for(int i = 1; i <= n; i++)
		cout << ans[i] << '\n';
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5252 KB Output is correct
7 Correct 4 ms 5116 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5160 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 4 ms 5220 KB Output is correct
14 Correct 4 ms 5200 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 3 ms 5136 KB Output is correct
17 Correct 4 ms 5196 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 4 ms 5324 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 4 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 4 ms 5228 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 4 ms 5196 KB Output is correct
30 Correct 4 ms 5068 KB Output is correct
31 Correct 4 ms 5196 KB Output is correct
32 Correct 5 ms 5196 KB Output is correct

Subtask #2
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 131 ms 10672 KB Output is correct
2 Correct 179 ms 21936 KB Output is correct
3 Correct 23 ms 8132 KB Output is correct
4 Correct 318 ms 17852 KB Output is correct
5 Correct 379 ms 37308 KB Output is correct
6 Correct 339 ms 27328 KB Output is correct
7 Correct 251 ms 17856 KB Output is correct
8 Correct 278 ms 19844 KB Output is correct
9 Correct 265 ms 19116 KB Output is correct
10 Correct 283 ms 19012 KB Output is correct
11 Correct 138 ms 18464 KB Output is correct
12 Correct 346 ms 29952 KB Output is correct
13 Correct 296 ms 27452 KB Output is correct
14 Correct 321 ms 26808 KB Output is correct
15 Correct 122 ms 18324 KB Output is correct
16 Correct 299 ms 31260 KB Output is correct
17 Correct 305 ms 27696 KB Output is correct

Subtask #3
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 237 ms 13580 KB Output is correct
2 Correct 343 ms 34748 KB Output is correct
3 Correct 27 ms 8784 KB Output is correct
4 Correct 281 ms 19448 KB Output is correct
5 Correct 374 ms 39936 KB Output is correct
6 Correct 345 ms 29256 KB Output is correct
7 Correct 270 ms 19540 KB Output is correct
8 Correct 297 ms 23576 KB Output is correct
9 Correct 290 ms 22120 KB Output is correct
10 Correct 292 ms 21048 KB Output is correct
11 Correct 218 ms 19784 KB Output is correct
12 Correct 360 ms 35716 KB Output is correct
13 Correct 328 ms 28116 KB Output is correct
14 Correct 319 ms 28224 KB Output is correct
15 Correct 140 ms 19640 KB Output is correct
16 Correct 295 ms 33428 KB Output is correct
17 Correct 309 ms 29420 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5068 KB Output is correct
3 Correct 3 ms 5068 KB Output is correct
4 Correct 4 ms 5196 KB Output is correct
5 Correct 4 ms 5068 KB Output is correct
6 Correct 4 ms 5252 KB Output is correct
7 Correct 4 ms 5116 KB Output is correct
8 Correct 4 ms 5068 KB Output is correct
9 Correct 4 ms 5160 KB Output is correct
10 Correct 4 ms 5156 KB Output is correct
11 Correct 4 ms 5068 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 4 ms 5220 KB Output is correct
14 Correct 4 ms 5200 KB Output is correct
15 Correct 4 ms 5196 KB Output is correct
16 Correct 3 ms 5136 KB Output is correct
17 Correct 4 ms 5196 KB Output is correct
18 Correct 6 ms 5196 KB Output is correct
19 Correct 4 ms 5068 KB Output is correct
20 Correct 4 ms 5324 KB Output is correct
21 Correct 4 ms 5196 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 4 ms 5068 KB Output is correct
24 Correct 4 ms 5068 KB Output is correct
25 Correct 4 ms 5068 KB Output is correct
26 Correct 4 ms 5068 KB Output is correct
27 Correct 4 ms 5228 KB Output is correct
28 Correct 4 ms 5196 KB Output is correct
29 Correct 4 ms 5196 KB Output is correct
30 Correct 4 ms 5068 KB Output is correct
31 Correct 4 ms 5196 KB Output is correct
32 Correct 5 ms 5196 KB Output is correct
33 Correct 131 ms 10672 KB Output is correct
34 Correct 179 ms 21936 KB Output is correct
35 Correct 23 ms 8132 KB Output is correct
36 Correct 318 ms 17852 KB Output is correct
37 Correct 379 ms 37308 KB Output is correct
38 Correct 339 ms 27328 KB Output is correct
39 Correct 251 ms 17856 KB Output is correct
40 Correct 278 ms 19844 KB Output is correct
41 Correct 265 ms 19116 KB Output is correct
42 Correct 283 ms 19012 KB Output is correct
43 Correct 138 ms 18464 KB Output is correct
44 Correct 346 ms 29952 KB Output is correct
45 Correct 296 ms 27452 KB Output is correct
46 Correct 321 ms 26808 KB Output is correct
47 Correct 122 ms 18324 KB Output is correct
48 Correct 299 ms 31260 KB Output is correct
49 Correct 305 ms 27696 KB Output is correct
50 Correct 237 ms 13580 KB Output is correct
51 Correct 343 ms 34748 KB Output is correct
52 Correct 27 ms 8784 KB Output is correct
53 Correct 281 ms 19448 KB Output is correct
54 Correct 374 ms 39936 KB Output is correct
55 Correct 345 ms 29256 KB Output is correct
56 Correct 270 ms 19540 KB Output is correct
57 Correct 297 ms 23576 KB Output is correct
58 Correct 290 ms 22120 KB Output is correct
59 Correct 292 ms 21048 KB Output is correct
60 Correct 218 ms 19784 KB Output is correct
61 Correct 360 ms 35716 KB Output is correct
62 Correct 328 ms 28116 KB Output is correct
63 Correct 319 ms 28224 KB Output is correct
64 Correct 140 ms 19640 KB Output is correct
65 Correct 295 ms 33428 KB Output is correct
66 Correct 309 ms 29420 KB Output is correct
67 Correct 23 ms 6816 KB Output is correct
68 Correct 104 ms 19764 KB Output is correct
69 Correct 157 ms 19524 KB Output is correct
70 Correct 275 ms 17860 KB Output is correct
71 Correct 350 ms 37396 KB Output is correct
72 Correct 328 ms 27432 KB Output is correct
73 Correct 269 ms 17884 KB Output is correct
74 Correct 291 ms 21456 KB Output is correct
75 Correct 272 ms 19488 KB Output is correct
76 Correct 266 ms 19284 KB Output is correct
77 Correct 186 ms 18108 KB Output is correct
78 Correct 342 ms 32016 KB Output is correct
79 Correct 292 ms 29904 KB Output is correct
80 Correct 284 ms 25560 KB Output is correct
81 Correct 113 ms 18216 KB Output is correct
82 Correct 292 ms 31164 KB Output is correct
83 Correct 316 ms 27588 KB Output is correct
84 Correct 286 ms 18168 KB Output is correct
85 Correct 359 ms 38076 KB Output is correct
86 Correct 329 ms 27804 KB Output is correct
87 Correct 265 ms 18216 KB Output is correct
88 Correct 277 ms 22196 KB Output is correct
89 Correct 277 ms 20292 KB Output is correct
90 Correct 272 ms 19652 KB Output is correct
91 Correct 195 ms 18476 KB Output is correct
92 Correct 358 ms 37304 KB Output is correct
93 Correct 302 ms 25000 KB Output is correct
94 Correct 306 ms 23096 KB Output is correct
95 Correct 131 ms 18744 KB Output is correct
96 Correct 284 ms 31756 KB Output is correct
97 Correct 296 ms 28244 KB Output is correct
98 Correct 266 ms 19468 KB Output is correct
99 Correct 370 ms 38508 KB Output is correct
100 Correct 342 ms 29080 KB Output is correct
101 Correct 266 ms 18712 KB Output is correct
102 Correct 297 ms 21860 KB Output is correct
103 Correct 285 ms 20768 KB Output is correct
104 Correct 271 ms 20164 KB Output is correct
105 Correct 196 ms 19036 KB Output is correct
106 Correct 323 ms 30200 KB Output is correct
107 Correct 290 ms 30520 KB Output is correct
108 Correct 318 ms 25412 KB Output is correct
109 Correct 123 ms 19352 KB Output is correct
110 Correct 294 ms 32500 KB Output is correct
111 Correct 305 ms 29108 KB Output is correct