Submission #838064

#	Time	Username	Problem	Language	Result	Execution time	Memory
838064		MohamedAhmed04	Capital City (JOI20_capital_city)	C++14	100 / 100	271 ms	62504 KiB

capital_city

#include <bits/stdc++.h>

using namespace std ;

const int MAX = 2e5 + 10 ;

int arr[MAX] ;
int n , k ;

vector< vector<int> >adj(MAX) ;

int dep[MAX] , P[MAX][20] ;

void dfs(int node , int par)
{
	P[node][0] = par ;
	for(int i = 1 ; i < 20 ; ++i)
		P[node][i] = P[P[node][i-1]][i-1] ;
	for(auto &child : adj[node])
	{
		if(child == par)
			continue ;
		dep[child] = dep[node] + 1 ;
		dfs(child , node) ;
	}
}

int LCA(int x , int y)
{
	if(dep[x] < dep[y])
		swap(x , y) ;
	for(int i = 19 ; i >= 0 ; --i)
	{
		if(dep[x] - (1 << i) >= dep[y])
			x = P[x][i] ;
	}
	if(x == y)
		return x ;
	for(int i = 19 ; i >= 0 ; --i)
	{
		if(P[x][i] != P[y][i])
			x = P[x][i] , y = P[y][i] ;
	}
	return P[x][0] ;
}

int lca[MAX] ;

vector< vector<int> >adj2(MAX) , adj2R(MAX) ;
int vis[MAX] ;

vector<int>topo ;

void dfs2(int node)
{
	vis[node] = 1 ;
	for(auto &child : adj2[node])
	{
		if(vis[child])
			continue ;
		dfs2(child) ;
	}
	topo.push_back(node) ;
}

bool flag ;
int comp[MAX] , curcmp ;
int cnt ;

vector<int>v ;

void dfs2_rev(int node)
{
	vis[node] = 1 , comp[node] = curcmp , cnt++ ;
	v.push_back(node) ;
	for(auto &child : adj2R[node])
	{
		if(vis[child])
			continue ;
		dfs2_rev(child) ;
	}
}

int main()
{
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>k ;
	for(int i = 0 ; i < n-1 ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	for(int i = 1 ; i <= n ; ++i)
		cin>>arr[i] ;
	dfs(1 , -1) ;
	for(int i = 1 ; i <= n ; ++i)
	{
		if(!lca[arr[i]])
			lca[arr[i]] = i ;
		else
			lca[arr[i]] = LCA(lca[arr[i]] , i) ;
	}
	for(int i = 2 ; i <= n ; ++i)
	{
		if(arr[P[i][0]] != arr[i] && lca[arr[i]] != i)
			adj2[arr[i]].push_back(arr[P[i][0]]) , adj2R[arr[P[i][0]]].push_back(arr[i]) ;
	}
	for(int i = 1 ; i <= k ; ++i)
	{
		if(!vis[i])
			dfs2(i) ;
	}
	memset(vis , 0 , sizeof(vis)) ;
	reverse(topo.begin() , topo.end()) ;
	int ans = n ;
	for(auto &node : topo)
	{
		if(vis[node])
			continue ;
		v.clear() ;
		flag = true , cnt = 0 , curcmp++ ;
		dfs2_rev(node) ;
		for(auto &node2 : v)
		{
			for(auto &child : adj2[node2])
				flag &= (comp[child] == curcmp) ;
		}
		if(flag)
			ans = min(ans , cnt-1) ;
	}
	return cout<<ans<<"\n" , 0 ;
}		

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