Submission #289340

#	Time	Username	Problem	Language	Result	Execution time	Memory
289340		TadijaSebez	Capital City (JOI20_capital_city)	C++11	100 / 100	1140 ms	66296 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
const int N=200050;
const int L=18;
int up[N],lca[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],head[N],lid[N],rid[N],sz[N],tme;
void Tree(int u,int p){
	par[u][0]=p;
	dep[u]=dep[p]+1;
	sz[u]=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),sz[u]+=sz[v];
}
void HLD(int u,int p){
	if(!head[u])head[u]=u;
	lid[u]=++tme;
	int hc=0;
	for(int v:E[u])if(v!=p&&(!hc||sz[hc]<sz[v]))hc=v;
	if(hc)head[hc]=head[u],HLD(hc,u);
	for(int v:E[u])if(v!=p&&v!=hc)HLD(v,u);
	rid[u]=tme;
}
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];
}
const int M=2*N;
pii st[M];
pii operator + (pii a,pii b){return {min(a.first,b.first),a.second+b.second};}
int ls[M],rs[M],tsz,root;
void Set(int&c,int ss,int se,int qi,pii x){
	if(!c)c=++tsz;
	if(ss==se){st[c]=x;return;}
	int mid=ss+se>>1;
	if(qi<=mid)Set(ls[c],ss,mid,qi,x);
	else Set(rs[c],mid+1,se,qi,x);
	st[c]=st[ls[c]]+st[rs[c]];
}
pii Get(int c,int ss,int se,int qs,int qe){
	if(qs>qe||ss>qe||qs>se)return {N,0};
	if(qs<=ss&&qe>=se)return st[c];
	int mid=ss+se>>1;
	return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe);
}
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[lca[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])Set(root,1,tme,lid[i],{disc[col],0});
}
void DelHLD(int col){
	for(int i:nodes[col])Set(root,1,tme,lid[i],{N,1});
}
pii GetHLD(int col){
	pii ans={N,0};
	for(int i:nodes[col]){
		for(int j=i;dep[j]>=dep[lca[col]];j=par[head[j]][0]){
			ans=ans+Get(root,1,tme,max(lid[head[j]],lid[lca[col]]),lid[j]);
		}
	}
	return ans;
}
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]);
	}
	pii tmp=GetHLD(u);
	low[u]=min(low[u],tmp.first);
	has_out[u]=tmp.second>0;
	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;
	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);
	HLD(1,0);
	st[0]={N,0};
	for(int i=1;i<=n;i++)Set(root,1,n,i,{N,0});
	for(int i=1;i<=n;i++)scanf("%i",&c[i]),nodes[c[i]].pb(i);
	for(int i=1;i<=k;i++){
		lca[i]=nodes[i][0];
		for(int j:nodes[i])lca[i]=LCA(lca[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 'void Set(int&, int, int, int, std::pair<int, int>)':
capital_city.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |  int mid=ss+se>>1;
      |          ~~^~~
capital_city.cpp: In function 'std::pair<int, int> Get(int, int, int, int, int)':
capital_city.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |  int mid=ss+se>>1;
      |          ~~^~~
capital_city.cpp: In function 'int Get(int)':
capital_city.cpp:54:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  while(ptr[col]<nodes[col].size()&&dep[Find(nodes[col][ptr[col]])]<dep[lca[col]])ptr[col]++;
      |        ~~~~~~~~^~~~~~~~~~~~~~~~~~
capital_city.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  if(ptr[col]==nodes[col].size())return 0;
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~
capital_city.cpp: In function 'void DFS(int)':
capital_city.cpp:83:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   83 |  while(v=Get(u)){
      |        ~^~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  scanf("%i %i",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~~
capital_city.cpp:108:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |  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:113:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |  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: 30 / 30
• Subtask 4: 59 / 59