oj.uz

Submission #562811

# Submission time Handle Problem Language Result Execution time Memory
562811 2022-05-15T10:29:16 Z Mazaalai Capital City (JOI20_capital_city) C++17
30 / 100
 146 ms 27832 KB 
#include <bits/stdc++.h>
#define LINE "--------------\n"
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
const int K = 2e5 + 5;
const int INF = 1.07e9;
int n, k;
vector <int> paths[N];
int city[N], pos[N];
vector <int> nums;

void dfs(int pos, int par = 0) {
	nums.pb(city[pos]);
	for (auto el : paths[pos]) {
		if (el != par) dfs(el, pos);
	}
}
int ans[N], ansVal[N];
int cnt[K], l[K], r[K];
int rs[K];

int find(int a) {
	if (ans[a] == a) return a;
	return ans[a] = find(ans[a]);
}
void merge(int a, int b) {
	a = find(a);
	b = find(b);
	rs[a] = rs[b] = max(rs[a], rs[b]);
	if (a == b) return;
	ans[b] = a;
	ansVal[a] += ansVal[b]+1;

}
signed main() {
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	// freopen("0.in", "r", stdin);
	// freopen("0.out", "w", stdout);
	cin >> n >> k;
	for (int i = 1; i < n; i++) {
		int a, b; cin >> a >> b;
		paths[a].pb(b);
		paths[b].pb(a);
	}
	for (int i = 1; i <= n; i++) cin >> city[i];
	int leaf = 1;
	for (int i = 1; i <= n; i++) leaf = (paths[i].size() == 1 ? i : leaf);
	nums.pb(-1);
	dfs(leaf);
	stack <int> stk;
	iota(ans+1, ans+1+n, 1);
	// check 0 
	for (int i = 1; i <= k; i++) {
		cnt[i] = 0; l[i] = n+1, r[i] = 0;
	}
	for (int i = 1; i <= n; i++) {
		cnt[nums[i]]++;
		l[nums[i]] = min(l[nums[i]], i);
		r[nums[i]] = i;
	}
	int res = INF;
	for (int i = 1; i <= k; i++) {
		rs[i] = r[i];
		if (cnt[i] == 0) continue;
		if (cnt[i] > r[i] - l[i]) res = 0;
	}
	for (int i = 1; i <= n; i++) {
		int x = nums[i];
		while (!stk.empty() && pos[x] != 0 && stk.top() >= pos[x])  {
			merge(nums[i], nums[stk.top()]);
			stk.pop();
		}
		stk.push(i);
		pos[x] = i;
		// cout << LINE;
		// cout << x << '\n';
		// for (int j = 1; j <= k; j++) cout << find(j) << " \n"[j==k];
		// for (int j = 1; j <= k; j++) cout << rs[find(j)] << " \n"[j==k];
		// for (int j = 1; j <= k; j++) cout << ansVal[find(j)] << " \n"[j==k];

		if (i == rs[find(x)]) {
			// cout << "HERE\n";
			res = min(res, ansVal[find(x)]);
		}
	}
	cout << res << '\n';
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5064 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5064 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5036 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 25744 KB Output is correct
2 Correct 74 ms 25780 KB Output is correct
3 Correct 96 ms 25796 KB Output is correct
4 Correct 72 ms 25784 KB Output is correct
5 Correct 101 ms 25484 KB Output is correct
6 Correct 85 ms 25756 KB Output is correct
7 Correct 100 ms 25296 KB Output is correct
8 Correct 76 ms 25312 KB Output is correct
9 Correct 109 ms 24212 KB Output is correct
10 Correct 113 ms 27736 KB Output is correct
11 Correct 114 ms 27800 KB Output is correct
12 Correct 111 ms 27800 KB Output is correct
13 Correct 119 ms 27832 KB Output is correct
14 Correct 108 ms 27712 KB Output is correct
15 Correct 106 ms 27812 KB Output is correct
16 Correct 107 ms 27728 KB Output is correct
17 Correct 146 ms 27812 KB Output is correct
18 Correct 110 ms 27720 KB Output is correct
19 Correct 109 ms 27776 KB Output is correct
20 Correct 114 ms 27780 KB Output is correct
21 Correct 3 ms 5036 KB Output is correct

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4948 KB Output is correct
4 Correct 3 ms 5064 KB Output is correct
5 Correct 3 ms 5036 KB Output is correct
6 Correct 3 ms 4948 KB Output is correct
7 Incorrect 3 ms 5036 KB Output isn't correct
8 Halted 0 ms 0 KB -