Submission #218188

#	Time	Username	Problem	Language	Result	Execution time	Memory
218188		mieszko11b	Capital City (JOI20_capital_city)	C++14	100 / 100	2898 ms	431420 KiB

capital_city

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;

#define X first
#define Y second

int n, k, m;
int c[200007];
vector<int> G[200007];
vector<ii> C[200007];
vector<ii> E;
vector<int> G2[4000007];
int num[20][200007], jp[20][200007];
int nxt = 1;
int ord[200007];
int h[200007];
vector<int> topo;
bool vis[4000007];
int scc[4000007], scc_size[4000007];
int scc_cnt;

void dfs(int w) {
	ord[w] = nxt++;
	for(int u : G[w]) {
		if(u != jp[0][w]) {
			jp[0][u] = w;
			h[u] = h[w] + 1;
			dfs(u);
		}
	}
}

void mark_path(int a, int b, int c) {
	if(h[a] < h[b])
		swap(a, b);
		
	for(int j = 17 ; j >= 0 ; j--) {
		if(h[jp[j][a]] >= h[b]) {
			E.emplace_back(c, num[j][a]);
			a = jp[j][a];
		}
	}
	
	if(a == b)
		return ;
		
	for(int j = 17 ; j >= 0 ; j--) {
		if(jp[j][a] != jp[j][b]) {
			E.emplace_back(c, num[j][a]);
			E.emplace_back(c, num[j][b]);
			a = jp[j][a];
			b = jp[j][b];
		}
	}
	
	E.emplace_back(c, num[0][a]);
}

void dfs2(int w) {
	if(vis[w])
		return ;
	vis[w] = 1;
	for(int u : G2[w])
		dfs2(u);
	topo.push_back(w);
}

void dfs3(int w) {
	for(int u : G2[w]) {
		if(!scc[u]) {
			scc[u] = scc[w];
			if(u && u <= k)
				scc_size[scc[u]]++;
			dfs3(u);
		}
	}
}

int main() {
	scanf("%d%d", &n, &k);
	for(int i = 1 ; i < n ; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		G[a].push_back(b);
		G[b].push_back(a);
	}
	for(int i = 1 ; i <= n ; i++)
		scanf("%d", &c[i]);

	h[1] = 1;
	dfs(1);
		
	m = k;
	
	for(int i = 1 ; i <= n ; i++) {
		num[0][i] = ++m;
		//~ E.emplace_back(num[0][i], c[i]);
		if(jp[0][i])
			E.emplace_back(num[0][i], c[jp[0][i]]);
	}
	
	for(int j = 1 ; j <= 17 ; j++) {
		for(int i = 1 ; i <= n ; i++) {
			num[j][i] = ++m;
			jp[j][i] = jp[j - 1][jp[j - 1][i]];
			E.emplace_back(num[j][i], num[j - 1][i]);
			E.emplace_back(num[j][i], num[j - 1][jp[j - 1][i]]);
		}
	}
	
	for(int i = 1 ; i <= n ; i++)
		C[c[i]].emplace_back(ord[i], i);
		
	for(int i = 1 ; i <= k ; i++) {
		sort(C[i].begin(), C[i].end());
		for(int j = 0 ; j + 1 < C[i].size() ; j++)
			mark_path(C[i][j].Y, C[i][j + 1].Y, i);
	}
	
	for(auto p : E) {
		//~ cout << p.X << " " << p.Y << endl;
		G2[p.X].push_back(p.Y);
	}
		
	for(int i = 1 ; i <= m ; i++)
		if(!vis[i])
			dfs2(i);
	
	reverse(topo.begin(), topo.end());
	
	for(int i = 1 ; i <= m ; i++)
		G2[i].clear();
		
	for(auto p : E)
		G2[p.Y].push_back(p.X);
	
	for(int w : topo) {
		if(!scc[w]) {
			scc[w] = ++scc_cnt;
			if(w && w <= k)
				scc_size[scc[w]]++;
			dfs3(w);
		}
	}
	
	//~ for(int i = 0 ; i <= m ; i++)
		//~ cout << i << ": " << scc[i] << endl;
	
	for(auto p : E)
		if(scc[p.X] != scc[p.Y])
			scc_size[scc[p.X]] = 0;
	
	int res = 1e9;
	for(int i = 1 ; i <= scc_cnt ; i++) {
		//~ cout << i << " " << " " << scc_size[i] << endl;
		if(scc_size[i])
			res = min(res, scc_size[i] - 1);
	}
	
	printf("%d\n", res);
	
	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:119:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j + 1 < C[i].size() ; j++)
                   ~~~~~~^~~~~~~~~~~~~
capital_city.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &c[i]);
   ~~~~~^~~~~~~~~~~~~

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