oj.uz

Submission #1015563

# Submission time Handle Problem Language Result Execution time Memory
1015563 2024-07-06T14:11:29 Z THXuan Capital City (JOI20_capital_city) C++14
0 / 100
 3000 ms 29008 KB 
// subtask 1 && subtask 2
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e9
using namespace std;
typedef long long ll;

int v[200005], p[200005];
vector<int>adj[200005], c[200005];

void dfs(int s, int e) {
	for (auto u : adj[s]) {
		if (u == e) continue;
		p[u] = s;
		dfs(u, s);
	}
}

void solve()
{
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n - 1; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
		c[v[i]].push_back(i);
	}
	dfs(1, 0);
	int ans = INF;
	for (int i = 1; i <= k; i++) {
		queue<int>q;
		for (auto u : c[i]) {q.push(u); }
		vector<bool>visited(k + 1, false);
		visited[i] = true;
		int anss = 0;
		while (q.size()) {
			int u = q.front(); q.pop();
			if (p[u] != 0 && v[p[u]] != v[u] && !visited[v[p[u]]]) {
				visited[v[p[u]]] = true;
				++anss;
				for (auto x : c[v[p[u]]])q.push(x);
			}
		}
		ans = min(ans, anss);
	}
	cout << ans << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;//cin>>t;
	while (t--) solve();
	return 0;
}

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3050 ms 29008 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

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