oj.uz

Submission #750354

# Submission time Handle Problem Language Result Execution time Memory
750354 2023-05-29T12:23:38 Z Dan4Life Capital City (JOI20_capital_city) C++17
0 / 100
 563 ms 38844 KB 
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(a) begin(a),end(a)
const int mxN = (int)2e5+2;

vector<int> v[mxN];
int n, m, ans = mxN;
int col[mxN], sub[mxN], par[mxN], vis[mxN], vis2[mxN];
vector<int> adj[mxN];

int getSub(int s, int p){
	sub[s] = 1; par[s]=p;
	for(auto u : adj[s])
		if(u!=p 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 p, bool ok){
	par[s] = ok?p:-1;
	for(auto u : adj[s])
		if(u!=p and !vis[u]) dfs(u,s,ok);
}

void cenDec(int cen, int p){
	cen = findCen(cen,p,getSub(cen,cen)); 
	dfs(cen,cen,1); vis[cen]=vis2[col[cen]]=1;
	queue<int> Q = queue<int>();
	bool ok = 1; int cnt = 0;
	for(auto u : v[col[cen]]){
		if(ok and par[u]>=0) Q.push(u);
		else ok=0;
	}
	while(!Q.empty() and ok){
		auto a = Q.front(); Q.pop();
		int C = col[a], Cp = col[par[a]];
		if(!vis2[Cp]){
			for(auto u : v[Cp]){
				if(ok and par[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!=p 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 >> col[i], v[col[i]].pb(i);
	cenDec(1,-1); cout << ans << "\n";
}

Compilation message

capital_city.cpp: In function 'void cenDec(int, int)':
capital_city.cpp:49:4: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   49 |    if(ok) vis2[Cp]=1; cnt++;
      |    ^~
capital_city.cpp:49:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   49 |    if(ok) vis2[Cp]=1; cnt++;
      |                       ^~~
capital_city.cpp:43:7: warning: unused variable 'C' [-Wunused-variable]
   43 |   int C = col[a], Cp = col[par[a]];
      |       ^

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9660 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 5 ms 9728 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 9724 KB Output is correct
7 Incorrect 6 ms 9856 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 9660 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 5 ms 9728 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 9724 KB Output is correct
7 Incorrect 6 ms 9856 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 563 ms 34736 KB Output is correct
2 Correct 187 ms 38820 KB Output is correct
3 Correct 518 ms 38224 KB Output is correct
4 Correct 199 ms 38844 KB Output is correct
5 Incorrect 552 ms 35808 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 9660 KB Output is correct
2 Correct 6 ms 9732 KB Output is correct
3 Correct 5 ms 9728 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 9724 KB Output is correct
7 Incorrect 6 ms 9856 KB Output isn't correct
8 Halted 0 ms 0 KB -