Submission #727009

#	Time	Username	Problem	Language	Result	Execution time	Memory
727009		nishkarsh	Capital City (JOI20_capital_city)	C++14	100 / 100	394 ms	47076 KiB

capital_city

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
using namespace std;
ll powmod(ll base,ll exponent,ll mod){
	ll ans=1;
	if(base<0) base+=mod;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int INF = 2e9;
const ll INFLL = 4e18;
const int upperlimit = 2e5+1;
const int mod = 1e9+7;
struct DirectedGraph{
	int n;
	vector<vector<int>> adj;
	vector<vector<int>> compladj;
	vector<int> topsort;
	vector<bool> visited;
	vector<bool> marked;
	DirectedGraph(int _n){
		n = _n;
		adj.resize(n);
		compladj.resize(n);
		visited.assign(n,false);
		marked.assign(n,false);
	}
	void add_edge(int &a,int &b){
		adj[a].pb(b);
		compladj[b].pb(a);
	}
	void topsort_dfs(int node){
		visited[node] = true;
		for(int i : compladj[node]) if(! visited[i]) topsort_dfs(i);
		topsort.pb(node);
	}
	void scc_dfs(int node, int &sz, bool &is_end, vi &node_list){
		sz++;
		node_list.pb(node);
		visited[node] = true;
		for(int i : adj[node]){
			if(marked[i]) is_end = false;
			else if(! visited[i]) scc_dfs(i,sz,is_end,node_list);
		}
	}
	int calculate_ans(){
		for(int i = 0; i < n; i++) if(! visited[i]) topsort_dfs(i);
		reverse(topsort.begin(),topsort.end());
		visited.assign(n,false);
		int ans = n,sz;
		bool is_end;
		vi node_list;
		for(int i : topsort){
			if(! marked[i]){
				sz = 0;
				is_end = true;
				node_list.clear();
				scc_dfs(i,sz,is_end,node_list);
				for(int j : node_list) marked[j] = true;
				if(is_end) ans = min(ans,sz);
			}
		}
		return ans;
	}
};
vi adj[upperlimit];
int par[upperlimit];
vi indices[upperlimit];
int etl[upperlimit];
int etr[upperlimit];
int c[upperlimit];
int node_cnt = 0;
void dfs(int node,int p){
	par[node] = p;
	indices[c[node]].pb(etl[node] = ++node_cnt);
	for(int i : adj[node]) if(i != p) dfs(i,node);
	etr[node] = node_cnt;
}
int main() {
	int n,k,a,b;
	cin >> n >> k;
	for(int i = 1; i < n; i++){
		cin >> a >> b;
		a--;b--;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	for(int i = 0; i < n; i++){
		cin >> c[i];
		c[i]--;
	}
	DirectedGraph dg(k);
	dfs(0,-1);
	for(int i = 1; i < n; i++){
		if((indices[c[i]][0] < etl[i]) || (indices[c[i]].back() > etr[i])) dg.add_edge(c[i],c[par[i]]);
		if(lower_bound(indices[c[par[i]]].begin(),indices[c[par[i]]].end(),etl[i]) != upper_bound(indices[c[par[i]]].begin(),indices[c[par[i]]].end(),etr[i])) dg.add_edge(c[par[i]],c[i]);
	}
	cout << dg.calculate_ans() - 1;
	return 0;
}

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