Submission #289323

#	Time	Username	Problem	Language	Result	Execution time	Memory
289323		TadijaSebez	Capital City (JOI20_capital_city)	C++11	11 / 100	3068 ms	51064 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int L=18;
int up[N],head[N],c[N];
int Find(int x){return up[x]==x?x:up[x]=Find(up[x]);}
vector<int> nodes[N],E[N];
int par[N][L],dep[N];
void Tree(int u,int p){
	par[u][0]=p;
	dep[u]=dep[p]+1;
	for(int i=1;i<L;i++)par[u][i]=par[par[u][i-1]][i-1];
	for(int v:E[u])if(v!=p)Tree(v,u);
}
int LCA(int u,int v){
	if(dep[u]<dep[v])swap(u,v);
	for(int i=L-1;~i;i--)if(dep[par[u][i]]>=dep[v])u=par[u][i];
	for(int i=L-1;~i;i--)if(par[u][i]!=par[v][i])u=par[u][i],v=par[v][i];
	return u==v?v:par[v][0];
}
void Rem(int i){for(int j:nodes[i])up[j]=par[j][0];}
int ptr[N];
int Get(int col){
	while(ptr[col]<nodes[col].size()&&dep[Find(nodes[col][ptr[col]])]<dep[head[col]])ptr[col]++;
	if(ptr[col]==nodes[col].size())return 0;
	else return c[Find(nodes[col][ptr[col]])];
}
int disc[N],low[N],tid,ans;
stack<int> stk;
bool in[N],has_out[N];
int val[N];
void AddHLD(int col){
	for(int i:nodes[col])val[i]=disc[col];
}
void DelHLD(int col){
	for(int i:nodes[col])val[i]=N;
}
int TakeMin(int col){
	int ans=N;
	for(int i:nodes[col]){
		for(int j=par[i][0];dep[j]>=dep[head[col]]&&c[j]!=col;j=par[j][0]){
			ans=min(ans,val[j]);
		}
	}
	return ans;
}
int HasOut(int col){
	for(int i:nodes[col]){
		for(int j=par[i][0];dep[j]>=dep[head[col]]&&c[j]!=col;j=par[j][0]){
			if(!in[c[j]])return 1;
		}
	}
	return 0;
}
void DFS(int u){
	Rem(u);
	disc[u]=low[u]=++tid;
	stk.push(u);in[u]=1;
	AddHLD(u);
	int v;
	while(v=Get(u)){
		DFS(v);
		low[u]=min(low[u],low[v]);
	}
	//other edges...
	low[u]=min(low[u],TakeMin(u));
	has_out[u]=HasOut(u);
	if(low[u]==disc[u]){
		bool ok=1;
		int sz=0;
		do{
			v=stk.top();
			stk.pop();
			in[v]=0;
			DelHLD(v);
			if(has_out[v])ok=0;
			sz++;
		}while(v!=u);
		if(ok)ans=min(ans,sz-1);
	}
}
int main(){
	int n,k;
	scanf("%i %i",&n,&k);
	for(int i=1;i<=n;i++)up[i]=i,val[i]=N;
	for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
	Tree(1,0);
	for(int i=1;i<=n;i++)scanf("%i",&c[i]),nodes[c[i]].pb(i);
	for(int i=1;i<=k;i++){
		head[i]=nodes[i][0];
		for(int j:nodes[i])head[i]=LCA(head[i],j);
	}
	ans=n;
	for(int i=1;i<=k;i++)if(!disc[i])DFS(i);
	printf("%i\n",ans);
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int Get(int)':
capital_city.cpp:25:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  while(ptr[col]<nodes[col].size()&&dep[Find(nodes[col][ptr[col]])]<dep[head[col]])ptr[col]++;
      |        ~~~~~~~~^~~~~~~~~~~~~~~~~~
capital_city.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  if(ptr[col]==nodes[col].size())return 0;
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'void DFS(int)':
capital_city.cpp:62:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |  while(v=Get(u)){
      |        ~^~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   85 |  scanf("%i %i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:87:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   87 |  for(int i=1,u,v;i<n;i++)scanf("%i %i",&u,&v),E[u].pb(v),E[v].pb(u);
      |                          ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:89:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |  for(int i=1;i<=n;i++)scanf("%i",&c[i]),nodes[c[i]].pb(i);
      |                       ~~~~~^~~~~~~~~~~~

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