oj.uz

Submission #534796

# Submission time Handle Problem Language Result Execution time Memory
534796 2022-03-09T02:00:21 Z rk42745417 Unique Cities (JOI19_ho_t5) C++17
4 / 100
 2000 ms 72956 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 undo(stack<int, vector<int>> &del) {
	while(!del.empty())
		add(del.top()), del.pop();
}
void rem(stack<int, vector<int>> &del) {
	cnt[arr[cur.top()]]--;
	if(cnt[arr[cur.top()]] == 0)
		res--;
	del.push(cur.top());
	cur.pop();
}
void rem() {
	cnt[arr[cur.top()]]--;
	if(cnt[arr[cur.top()]] == 0)
		res--;
	cur.pop();
}
void cal_ans(int u, int p) {
	stack<int, vector<int>> del;
	multiset<int> has;
	for(int v : edge[u])
		if(v != p)
			has.insert(max_dep[v] + 1);
	has.insert(0);
	for(int v : edge[u]) {
		if(v == p || max_dep[v] + 1 != max_dep[u])
			continue;
		has.erase(has.lower_bound(max_dep[v] + 1));
		while(!cur.empty() && dep[cur.top()] >= dep[u] - *has.rbegin())
			rem(del);
		add(u);
		cal_ans(v, u);
		rem();
		has.insert(max_dep[v] + 1);
	}
	for(int v : edge[u]) {
		if(v == p || max_dep[v] + 1 == max_dep[u])
			continue;
		while(!cur.empty() && dep[cur.top()] >= dep[u] - max_dep[u])
			rem(del);
		add(u);
		cal_ans(v, u);
		rem();
	}

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

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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 18 ms 5248 KB Output is correct
4 Correct 18 ms 5388 KB Output is correct
5 Correct 5 ms 5168 KB Output is correct
6 Correct 52 ms 5708 KB Output is correct
7 Correct 17 ms 5324 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5156 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 4 ms 5196 KB Output is correct
13 Correct 45 ms 5580 KB Output is correct
14 Correct 8 ms 5324 KB Output is correct
15 Correct 9 ms 5288 KB Output is correct
16 Correct 7 ms 5252 KB Output is correct
17 Correct 26 ms 5452 KB Output is correct
18 Correct 19 ms 5416 KB Output is correct
19 Correct 6 ms 5080 KB Output is correct
20 Correct 72 ms 5716 KB Output is correct
21 Correct 18 ms 5348 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 6 ms 5196 KB Output is correct
24 Correct 5 ms 5156 KB Output is correct
25 Correct 4 ms 5160 KB Output is correct
26 Correct 4 ms 5196 KB Output is correct
27 Correct 28 ms 5624 KB Output is correct
28 Correct 23 ms 5452 KB Output is correct
29 Correct 15 ms 5416 KB Output is correct
30 Correct 7 ms 5196 KB Output is correct
31 Correct 32 ms 5572 KB Output is correct
32 Correct 18 ms 5396 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 12348 KB Output is correct
2 Execution timed out 2101 ms 44840 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 259 ms 16460 KB Output is correct
2 Execution timed out 2062 ms 72956 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 4 ms 5164 KB Output is correct
3 Correct 18 ms 5248 KB Output is correct
4 Correct 18 ms 5388 KB Output is correct
5 Correct 5 ms 5168 KB Output is correct
6 Correct 52 ms 5708 KB Output is correct
7 Correct 17 ms 5324 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5156 KB Output is correct
10 Correct 5 ms 5196 KB Output is correct
11 Correct 6 ms 5152 KB Output is correct
12 Correct 4 ms 5196 KB Output is correct
13 Correct 45 ms 5580 KB Output is correct
14 Correct 8 ms 5324 KB Output is correct
15 Correct 9 ms 5288 KB Output is correct
16 Correct 7 ms 5252 KB Output is correct
17 Correct 26 ms 5452 KB Output is correct
18 Correct 19 ms 5416 KB Output is correct
19 Correct 6 ms 5080 KB Output is correct
20 Correct 72 ms 5716 KB Output is correct
21 Correct 18 ms 5348 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 6 ms 5196 KB Output is correct
24 Correct 5 ms 5156 KB Output is correct
25 Correct 4 ms 5160 KB Output is correct
26 Correct 4 ms 5196 KB Output is correct
27 Correct 28 ms 5624 KB Output is correct
28 Correct 23 ms 5452 KB Output is correct
29 Correct 15 ms 5416 KB Output is correct
30 Correct 7 ms 5196 KB Output is correct
31 Correct 32 ms 5572 KB Output is correct
32 Correct 18 ms 5396 KB Output is correct
33 Correct 155 ms 12348 KB Output is correct
34 Execution timed out 2101 ms 44840 KB Time limit exceeded
35 Halted 0 ms 0 KB -