Submission #446236

#	Time	Username	Problem	Language	Result	Execution time	Memory
446236		kig9981	Capital City (JOI20_capital_city)	C++17	100 / 100	575 ms	85552 KiB

capital_city

#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<18;
vector<int> adj[2*SZ], V[2*SZ];
vector<pair<int,int>> E;
stack<int> S;
int node_cnt, scc_cnt, num[2*SZ], rev[200000], low[2*SZ], scc[2*SZ], W[200000], hld[200000], depth[200000], parent[200000], A[200000];
bool chk[2*SZ];

void dfs(int c)
{
	W[c]=1;
	for(auto n: adj[c]) if(W[n]==0) {
		parent[n]=c;
		depth[n]=depth[c]+1;
		dfs(n);
		W[c]+=W[n];
	}
}

void dfs2(int c)
{
	int mx=-1;
	V[A[c]].push_back(c);
	num[c]=node_cnt++;
	rev[num[c]]=c;
	for(auto n: adj[c]) if(W[n]<W[c] && (mx==-1 || W[mx]<W[n])) mx=n;
	if(mx==-1) return;
	hld[mx]=hld[c];
	dfs2(mx);
	for(auto n: adj[c]) if(W[n]<W[c] && mx!=n) dfs2(hld[n]=n);
}

void add_edge(int s, int e, int v)
{
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) adj[v].push_back(s++);
		if(~e&1) adj[v].push_back(e--);
	}
}

void add_edge(int a, int b)
{
	int r=SZ+num[b];
	while(hld[a]^hld[b]) {
		if(depth[hld[a]]<depth[hld[b]]) swap(a,b);
		add_edge(num[hld[a]],num[a],r);
		a=parent[hld[a]];
	}
	if(num[a]>num[b]) swap(a,b);
	add_edge(num[a],num[b],r);
}

void dfs3(int c)
{
	num[c]=low[c]=++node_cnt;
	chk[c]=true;
	S.push(c);
	for(auto n: adj[c]) {
		if(num[n]==0) {
			dfs3(n);
			low[c]=min(low[c],low[n]);
		}
		else if(chk[n]) low[c]=min(low[c],num[n]);
	}
	if(num[c]==low[c]) {
		while(chk[c]) {
			scc[S.top()]=scc_cnt;
			chk[S.top()]=false;
			S.pop();
		}
		scc_cnt++;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt","r",stdin));
	TEST(freopen("output.txt","w",stdout));
	TEST(freopen("debug.txt","w",stderr));
	int N, K, ans=0x7fffffff;
	cin>>N>>K;
	for(int i=1;i<N;i++) {
		int a, b;
		cin>>a>>b;
		adj[--a].push_back(--b);
		adj[b].push_back(a);
	}
	for(int i=0;i<N;i++) cin>>A[i], A[i]--;
	dfs(0); dfs2(0);
	for(int i=1;i<SZ;i++) {
		adj[i].clear();
		adj[i].push_back(2*i);
		adj[i].push_back(2*i+1);
	}
	for(int i=node_cnt=0;i<K;i++) {
		for(int j=1;j<V[i].size();j++) {
			add_edge(V[i][j-1],V[i][j]);
			adj[SZ+num[V[i][j-1]]].push_back(SZ+num[V[i][j]]);
			adj[SZ+num[V[i][j]]].push_back(SZ+num[V[i][j-1]]);
		}
		V[i].clear();
	}
	memset(num,0,sizeof(num));
	for(int i=2*SZ;--i;) if(num[i]==0) dfs3(i);
	memset(low,0,sizeof(low));
	for(int i=0;i<N;i++) V[scc[SZ+i]].push_back(A[rev[i]]);
	for(int i=2*SZ;--i;) {
		sort(V[i].begin(),V[i].end());
		V[i].resize(unique(V[i].begin(),V[i].end())-V[i].begin());
		for(auto n: adj[i]) if(scc[i]^scc[n]) low[scc[i]]++;
	}
	for(int i=0;i<scc_cnt;i++) if(low[i]==0 && V[i].size()) ans=min(ans,(int)V[i].size()-1);
	cout<<ans<<'\n';
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:109:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |   for(int j=1;j<V[i].size();j++) {
      |               ~^~~~~~~~~~~~

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