oj.uz

Submission #389026

# Submission time Handle Problem Language Result Execution time Memory
389026 2021-04-13T13:51:28 Z ogibogi2004 Capital City (JOI20_capital_city) C++14
1 / 100
 1084 ms 42096 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN=2e5+6;
int n,k;
int c[MAXN];
vector<int>g[MAXN];
vector<int>nodes[MAXN];
bool cantuse[MAXN];
int ans;
bool used[MAXN];
bool used1[MAXN];
bool used2[MAXN];
int subtree[MAXN],par[MAXN];
void dfs(int u,int p)
{
	par[u]=p;
	subtree[u]=1;
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		dfs(xd,u);
		subtree[u]+=subtree[xd];
	}
}
int find_centroid(int u,int p,int n1)
{
	for(auto xd:g[u])
	{
		if(xd==p)continue;
		if(used[xd])continue;
		if(subtree[xd]>n1/2)
		{
			return find_centroid(xd,u,n1);
		}
	}
	return u;
}
void solve(int u)
{
	dfs(u,0);
	int cen=find_centroid(u,0,subtree[u]);
	dfs(cen,0);
	queue<int>q;
	//cout<<"&& "<<u<<" "<<cen<<endl;
	if(cantuse[c[cen]]==0)
	{
		for(auto xd:nodes[c[cen]])
		{
			q.push(xd);
		}
		int cnt=1;
		vector<int>vc;
		vc.push_back(c[cen]);
		used2[c[cen]]=1;cantuse[c[cen]]=1;
		bool imposibel=0;
		while(!q.empty())
		{
			u=q.front();q.pop();
			//cout<<u<<" ";
			used1[u]=1;
			if(par[u]==0)continue;
			if(used1[par[u]]==0&&used2[c[par[u]]]==0&&cantuse[c[par[u]]])
			{
				imposibel=1;
				break;
			}
			if(used2[c[par[u]]]==0)
			{
				//cout<<" *"<<c[par[u]]<<"* ";
				used2[c[par[u]]]=1;vc.push_back(c[par[u]]);
				cantuse[c[par[u]]]=1;
				for(auto xd:nodes[c[par[u]]])
				{
					q.push(xd);
				}
				cnt++;
			}
		}
		//cout<<endl;
		//cout<<imposibel<<" "<<cnt<<endl;
		if(!imposibel)ans=min(ans,cnt);
		for(auto xd:vc)used2[xd]=0;
	}
	used[cen]=1;
	for(auto xd:g[cen])
	{
		if(used[xd]==0)
		{
			solve(xd);
		}
	}
}
int main()
{
	cin>>n>>k;
	ans=k;
	for(int i=1;i<n;i++)
	{
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++)
	{
		cin>>c[i];
		nodes[c[i]].push_back(i);
	}
	solve(1);
	cout<<ans-1<<endl;
return 0;
}

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 9 ms 9696 KB Output is correct
4 Correct 9 ms 9684 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9664 KB Output is correct
7 Correct 6 ms 9608 KB Output is correct
8 Correct 6 ms 9648 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9624 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 9 ms 9696 KB Output is correct
4 Correct 9 ms 9684 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9664 KB Output is correct
7 Correct 6 ms 9608 KB Output is correct
8 Correct 6 ms 9648 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9624 KB Output is correct
11 Incorrect 8 ms 9804 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1084 ms 41588 KB Output is correct
2 Correct 412 ms 42096 KB Output is correct
3 Correct 1075 ms 41480 KB Output is correct
4 Correct 388 ms 42096 KB Output is correct
5 Incorrect 679 ms 38236 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 59.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9816 KB Output is correct
2 Correct 7 ms 9676 KB Output is correct
3 Correct 9 ms 9696 KB Output is correct
4 Correct 9 ms 9684 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9664 KB Output is correct
7 Correct 6 ms 9608 KB Output is correct
8 Correct 6 ms 9648 KB Output is correct
9 Correct 6 ms 9676 KB Output is correct
10 Correct 6 ms 9624 KB Output is correct
11 Incorrect 8 ms 9804 KB Output isn't correct
12 Halted 0 ms 0 KB -