oj.uz

Submission #365806

# Submission time Handle Problem Language Result Execution time Memory
365806 2021-02-12T11:54:41 Z negar_a Capital City (JOI20_capital_city) C++14
1 / 100
 868 ms 34540 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;
bool cent[maxn], mark[maxn], com[maxn], visit[maxn];

void dfs(int v, int p = -1){
	sz[v] = 1;
	com[v] = true;
	for(int u : adj[v]){
		if(!cent[u] && u != p){
			dfs(u, 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 clean(int v, int p = -1){
	com[v] = par[v] = sz[v] = 0;
	for(int u : adj[v]){
		if(u != p && !cent[u])
			clean(u, v);
	}
}

void solve(int v){
	dfs(v);
	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);
		for(int u : vec[x]){
			if(!com[u]){
				flag = false;
				break;
			}
			if(par[u] != -1 && !mark[c[par[u]]]){
				if(!com[par[u]]){
					flag = false;
					break;
				}
				q.push(c[par[u]]);
				mark[c[par[u]]] = true;
			}
			if(!flag)
				break;
		}
	}
	if(flag){
		ans = min(ans, (int)vc.size() - 1);
	}
		
	//clear
	for(int u : vc)
		mark[u] = false;
	clean(v);
		
	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;
}
/*
6 3
2 1
3 5
6 2
3 4
2 3
1 3 1 2 3 2

8 4
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2 4 3 1 1 2 3 4

12 4
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3 1 1 2 4 3 3 2 2 3 4 4
*/

Compilation message

capital_city.cpp: In function 'void clean(int, int)':
capital_city.cpp:46:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   46 |  com[v] = par[v] = sz[v] = 0;
      |           ~~~~~~~^~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB Output is correct
2 Correct 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 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 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 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 9836 KB Output is correct
12 Correct 8 ms 9836 KB Output is correct
13 Correct 9 ms 9984 KB Output is correct
14 Correct 10 ms 9836 KB Output is correct
15 Correct 10 ms 9964 KB Output is correct
16 Correct 11 ms 9964 KB Output is correct
17 Correct 8 ms 9964 KB Output is correct
18 Correct 9 ms 10088 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 10 ms 9964 KB Output is correct
21 Correct 8 ms 9964 KB Output is correct
22 Correct 8 ms 9964 KB Output is correct
23 Correct 9 ms 9984 KB Output is correct
24 Correct 9 ms 9984 KB Output is correct
25 Incorrect 9 ms 9964 KB Output isn't correct
26 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 772 ms 34228 KB Output is correct
2 Correct 241 ms 34540 KB Output is correct
3 Correct 746 ms 33920 KB Output is correct
4 Correct 240 ms 34540 KB Output is correct
5 Correct 759 ms 31596 KB Output is correct
6 Correct 240 ms 34540 KB Output is correct
7 Correct 720 ms 31852 KB Output is correct
8 Correct 237 ms 34280 KB Output is correct
9 Incorrect 868 ms 30444 KB Output isn't correct
10 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 7 ms 9708 KB Output is correct
3 Correct 7 ms 9708 KB Output is correct
4 Correct 7 ms 9708 KB Output is correct
5 Correct 7 ms 9708 KB Output is correct
6 Correct 7 ms 9708 KB Output is correct
7 Correct 7 ms 9708 KB Output is correct
8 Correct 7 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 9836 KB Output is correct
12 Correct 8 ms 9836 KB Output is correct
13 Correct 9 ms 9984 KB Output is correct
14 Correct 10 ms 9836 KB Output is correct
15 Correct 10 ms 9964 KB Output is correct
16 Correct 11 ms 9964 KB Output is correct
17 Correct 8 ms 9964 KB Output is correct
18 Correct 9 ms 10088 KB Output is correct
19 Correct 8 ms 9964 KB Output is correct
20 Correct 10 ms 9964 KB Output is correct
21 Correct 8 ms 9964 KB Output is correct
22 Correct 8 ms 9964 KB Output is correct
23 Correct 9 ms 9984 KB Output is correct
24 Correct 9 ms 9984 KB Output is correct
25 Incorrect 9 ms 9964 KB Output isn't correct
26 Halted 0 ms 0 KB -