oj.uz

Submission #365791

# Submission time Handle Problem Language Result Execution time Memory
365791 2021-02-12T11:13:37 Z negar_a Capital City (JOI20_capital_city) C++14
1 / 100
 2059 ms 39404 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 2e5 + 5;
vector <int> adj[maxn], vec[maxn];
int sz[maxn], par[maxn], c[maxn];
int ans = INT_MAX;
bool cent[maxn], mark[maxn], com[maxn], visit[maxn];

void dfs(int v, bool f, int p = -1){
	sz[v] = 1;
	com[v] = f;
	for(int u : adj[v]){
		if(!cent[u] && u != p){
			dfs(u, f, v);
			sz[v] += sz[u];
		}
	}
}
int find_centroid(int v, int s, int p = -1){
	for(int u : adj[v]){
		if(!cent[u] && u != p && sz[u] > s / 2){
			return find_centroid(u, s, v);
		}
	}
	return v;
}
void dfs2(int v, int p = -1){
	for(int u : adj[v]){
		if(!cent[u] && u != p){
			par[u] = v;
			dfs2(u, v);
		}
	}
}

void solve(int v){
	dfs(v, 1);
	int cn = find_centroid(v, sz[v]);
//	cout << "cen : " << cn << endl; 
	
	par[cn] = -1;
	dfs2(cn);
	
	queue <int> q;
	vector <int> vc;
	
	q.push(c[cn]);
	bool flag = true; 
	mark[c[cn]] = true;
	while(q.size() && flag){
		int x = q.front();
		q.pop();
		vc.pb(x);
		if(visit[x])
			flag = false;
		for(int u : vec[x]){
			if(!com[u])
				flag = false;
			if(par[u] != -1 && !mark[c[par[u]]]){
				q.push(c[par[u]]);
				mark[c[par[u]]] = true;
			}
		}
	}
	visit[c[cn]] = true;
	if(flag){
		ans = min(ans, (int)vc.size() - 1);
	}
		
	//clear
	for(int u : vc)
		mark[u] = false;
	dfs(v, 0);
		
	cent[cn] = true;
	for(int u : adj[cn]){
		if(!cent[u]){
			solve(u);
		}
	}
}

int main(){
	fast_io;
	int n, k;
	cin >> n >> k;
	for(int i = 0; i < n - 1; i ++){
		int x, y;
		cin >> x >> y;
		x --; y --;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for(int i = 0; i < n; i ++){
		cin >> c[i];
		vec[c[i]].pb(i);
	}
	ans = k - 1;
	solve(0);
	cout << ans;
	
	return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 6 ms 9708 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 6 ms 9708 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 6 ms 9708 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 6 ms 9708 KB Output is correct
11 Correct 8 ms 9964 KB Output is correct
12 Correct 10 ms 9964 KB Output is correct
13 Correct 10 ms 9964 KB Output is correct
14 Correct 10 ms 9964 KB Output is correct
15 Incorrect 10 ms 10112 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 830 ms 37776 KB Output is correct
2 Correct 263 ms 38252 KB Output is correct
3 Correct 810 ms 37516 KB Output is correct
4 Correct 265 ms 38260 KB Output is correct
5 Correct 2059 ms 34668 KB Output is correct
6 Incorrect 269 ms 39404 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 6 ms 9708 KB Output is correct
3 Correct 6 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 6 ms 9708 KB Output is correct
6 Correct 6 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 6 ms 9708 KB Output is correct
9 Correct 7 ms 9708 KB Output is correct
10 Correct 6 ms 9708 KB Output is correct
11 Correct 8 ms 9964 KB Output is correct
12 Correct 10 ms 9964 KB Output is correct
13 Correct 10 ms 9964 KB Output is correct
14 Correct 10 ms 9964 KB Output is correct
15 Incorrect 10 ms 10112 KB Output isn't correct
16 Halted 0 ms 0 KB -