oj.uz

Submission #750372

# Submission time Handle Problem Language Result Execution time Memory
750372 2023-05-29T12:41:43 Z Dan4Life Capital City (JOI20_capital_city) C++17
0 / 100
 632 ms 35148 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int mxN = (int)2e5+2;
 
int n, m, ans = mxN;
vector<int> adj[mxN], v[mxN];
int C[mxN], sub[mxN], p[mxN], vis[mxN], vis2[mxN];
 
int getSub(int s, int par){
	sub[s] = 1; p[s]=par;
	for(auto u : adj[s])
		if(u!=par and !vis[u]) 
			sub[s]+=getSub(u,s);
	return sub[s];
}
 
int findCen(int s, int p, int n){
	for(auto u : adj[s])
		if(u!=p and !vis[u] and sub[u]>n/2)
			return findCen(u,s,n);
	return s;
}
 
void dfs(int s, int par, bool ok){
	p[s] = ok?par:-1;
	for(auto u : adj[s])
		if(u!=par and !vis[u]) dfs(u,s,ok);
}
 
void cenDec(int cen, int par){
	cen = findCen(cen,par,getSub(cen,cen)); 
	dfs(cen,cen,1); vis[cen]=vis2[C[cen]]=1;
	queue<int> Q = queue<int>();
	bool ok = 1; int cnt = 0;
	for(auto u : v[C[cen]]){
		if(ok and p[u]>=0) Q.push(u);
		else ok=0;
	}
	while(!Q.empty() and ok){
		auto a = Q.front(); Q.pop();
		int CP = C[p[a]];
		if(!vis2[CP]){
			for(auto u : v[CP]){
				if(ok and p[u]>=0) Q.push(u);
				else ok=0;
			}
			if(ok) vis2[CP]=1; cnt++;
		}
	}
	if(ok) ans = min(ans, cnt);
	dfs(cen,cen,0);
	for(auto u : adj[cen])
		if(u!=par and !vis[u]) cenDec(u,cen);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m; 
	for(int i = 1; i < n; i++){
		int a, b; cin >> a >> b;
		adj[a].pb(b), adj[b].pb(a);
	}
	for(int i = 1; i <= n; i++) 
		cin >> C[i], v[C[i]].pb(i);
	cenDec(1,-1); cout << ans << "\n";
}

Compilation message

capital_city.cpp: In function 'void cenDec(int, int)':
capital_city.cpp:48:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   48 |    if(ok) vis2[CP]=1; cnt++;
      |    ^~
capital_city.cpp:48:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   48 |    if(ok) vis2[CP]=1; cnt++;
      |                       ^~~

Subtask #1
0 / 1.0

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

Subtask #2
0 / 10.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 632 ms 34748 KB Output is correct
2 Correct 193 ms 35148 KB Output is correct
3 Correct 548 ms 34496 KB Output is correct
4 Correct 192 ms 35148 KB Output is correct
5 Incorrect 578 ms 32064 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

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