Submission #938181

#	Time	Username	Problem	Language	Result	Execution time	Memory
938181		pcc	Capital City (JOI20_capital_city)	C++14	100 / 100	853 ms	272904 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int C = 70;
const int mxn = 2e5+10;
vector<int> tree[mxn];
int par[mxn][20],id[mxn][20],dep[mxn];
int to[mxn*C],nid[mxn*C],head[mxn*C];
int col[mxn];
int N,K;
int ppp = 0;
int wei[mxn*C];
vector<int> v[mxn];
int pt;

namespace BUILD{
	void add_edge(int a,int b){
		ppp++;
		nid[ppp] = head[a];
		head[a] = ppp;
		to[ppp] = b;
		return;
	}

	void dfs(int now){
		id[now][0] = ++pt;
		add_edge(id[now][0],now);
		add_edge(id[now][0],par[now][0]);
		for(int i = 1;i<20;i++){
			id[now][i] = ++pt;
			par[now][i] = par[par[now][i-1]][i-1];
			add_edge(id[now][i],id[now][i-1]);
			add_edge(id[now][i],id[par[now][i-1]][i-1]);
		}
		for(auto nxt:tree[now]){
			if(nxt == par[now][0])continue;
			par[nxt][0] = now;
			dep[nxt] = dep[now]+1;
			dfs(nxt);
		}
		return;
	}
	int LCA(int a,int b){
		if(dep[a]<dep[b])swap(a,b);
		int d = dep[a]-dep[b];
		for(int i = 19;i>=0;i--){
			if(d&(1<<i))a = par[a][i];
		}
		for(int i = 19;i>=0;i--){
			if(par[a][i] != par[b][i])a = par[a][i],b = par[b][i];
		}
		return (a==b?a:par[a][0]);
	}

	void add(int a,int d){
		int now = a;
		for(int i = 19;i>=0;i--){
			if(d&(1<<i)){
				add_edge(a,id[now][i]);
				now = par[now][i];
			}
		}
		return;
	}

	void GO(){
		par[1][0] = 1;
		dfs(1);
		//cout<<"HH"<<endl;
		for(int i = 1;i<=K;i++){
			if(v[i].empty())continue;
			int now = v[i][0];
			for(auto &j:v[i]){
				add_edge(j,i+N);
				add_edge(i+N,j);
				now = LCA(now,j);
			}
			//cout<<i<<":"<<endl;for(auto &j:v[i])cout<<j<<',';cout<<now<<endl;
			for(auto &j:v[i]){
				add(j,dep[j]-dep[now]);
			}
		}
		return;
	}
	void PRINT(){
		for(int i = 1;i<=pt;i++){
			cout<<i<<":";
			for(int eid = head[i];eid;eid = nid[eid]){
				cout<<to[eid]<<',';
			}cout<<endl;
		}
		return;
	}

}

namespace SCC{
	int idx[mxn*C],low[mxn*C],cnt = 0,gid[mxn*C],gcnt = 0;
	vector<int> st;
	int in[mxn*C],out[mxn*C];
	int dp[mxn*C];
	bitset<mxn*C> vis;

	void dfs(int now){
		assert(!vis[now]);
		vis[now] = true;
		idx[now] = low[now] = ++cnt;
		st.push_back(now);
		for(int eid = head[now];eid;eid = nid[eid]){
			int nxt = to[eid];
			if(gid[nxt])continue;
			if(!idx[nxt]){
				dfs(nxt);
				low[now] = min(low[now],low[nxt]);
			}
			else low[now] = min(low[now],idx[nxt]);
		}
		if(idx[now] == low[now]){
			gcnt++;
			while(st.back() != now){
				gid[st.back()] = gcnt;
				st.pop_back();
			}
			gid[st.back()] = gcnt;
			st.pop_back();
		}
		return;
	}
	void GO(){
		for(int i = 1;i<=pt;i++){
			if(!gid[i])dfs(i);
		}
		return;
	}
	void GETANS(){
		for(int i = 1;i<=pt;i++){
			dp[gid[i]]+=wei[i];
			for(int eid = head[i];eid;eid = nid[eid]){
				int nxt = to[eid];
				if(gid[nxt] == gid[i])continue;
				out[gid[i]]++;
				in[gid[nxt]]++;
			}
		}
		int re = 1e9;
		for(int i = 1;i<=gcnt;i++){
			if(out[i])continue;
			re = min(re,dp[i]);
			//cout<<"SCC:"<<i<<":"<<dp[i]<<endl;
		}
		cout<<re-1<<'\n';
		return;
	}
	void PRINT(){
		for(int i = 1;i<=pt;i++){
			cout<<i<<":"<<gid[i]<<endl;
		}
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>K;
	for(int i = 1;i<N;i++){
		int a,b;
		cin>>a>>b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	for(int i = 1;i<=N;i++){
		cin>>col[i];
		v[col[i]].push_back(i);
	}
	for(int i = 1;i<=K;i++)wei[i+N] = 1;
	pt = N+K;
	//cout<<"HI"<<endl;
	BUILD::GO();
	//BUILD::PRINT();
	//cout<<"HI"<<endl;
	SCC::GO();
	//if(N>2000)return 0;
	//cout<<"HI"<<endl;
	//SCC::PRINT();
	SCC::GETANS();
}

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