Submission #565292

#	Time	Username	Problem	Language	Result	Execution time	Memory
565292		MilosMilutinovic	Capital City (JOI20_capital_city)	C++14	100 / 100	794 ms	41496 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
const int N=200050;
int n,k,a[N],sz[N],cnt[N],par[N],ans;
bool was[N],clr[N];
vector<int> E[N],ids[N];
void DFS(int u,int p){sz[u]=1;for(int v:E[u])if(!was[v]&&v!=p)DFS(v,u),sz[u]+=sz[v];}
int Find(int u,int p,int n){for(int v:E[u])if(!was[v]&&v!=p&&sz[v]*2>=n)return Find(v,u,n);return u;}
int Find(int u){DFS(u,u);u=Find(u,u,sz[u]);was[u]=1;return u;}
void Clr(int u,int p){
	par[u]=p;
	cnt[a[u]]=0;
	clr[a[u]]=false;
	for(int v:E[u])if(!was[v]&&v!=p)Clr(v,u);
}
void DFS1(int u,int p){
	cnt[a[u]]++;
	for(int v:E[u])if(!was[v]&&v!=p)DFS1(v,u);
}
void Solve(int u){
	u=Find(u);
	Clr(u,u);
	DFS1(u,u);
	int cc=0;
	stack<int> stk;
	stk.push(a[u]);
	while(!stk.empty()){
		int x=stk.top();
		stk.pop();
		if(clr[x])continue;
		if(cnt[x]!=ids[x].size()){cc=1e9;break;}
		clr[x]=true;
		cc++;
		for(int v:ids[x])stk.push(a[par[v]]);
	}
	ans=min(ans,cc-1);
	for(int v:E[u])if(!was[v])Solve(v);
}
int main(){
	scanf("%i%i",&n,&k);
	for(int i=1;i<n;i++){
		int u,v;scanf("%i%i",&u,&v);
		E[u].push_back(v);
		E[v].push_back(u);
	}
	for(int i=1;i<=n;i++)scanf("%i",&a[i]),ids[a[i]].push_back(i);
	ans=1e9;
	Solve(1);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void Solve(int)':
capital_city.cpp:31:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   if(cnt[x]!=ids[x].size()){cc=1e9;break;}
      |      ~~~~~~^~~~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  scanf("%i%i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:42:16: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |   int u,v;scanf("%i%i",&u,&v);
      |           ~~~~~^~~~~~~~~~~~~~
capital_city.cpp:46:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  for(int i=1;i<=n;i++)scanf("%i",&a[i]),ids[a[i]].push_back(i);
      |                       ~~~~~^~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 59 / 59