Submission #216732

#	Time	Username	Problem	Language	Result	Execution time	Memory
216732		ainta	Capital City (JOI20_capital_city)	C++17	100 / 100	962 ms	174600 KiB

capital_city

#include<cstdio>
#include<algorithm>
#include<vector>
#define N_ 210000
#define M_ 1010000
using namespace std;
vector<int>E[N_], G[M_], P[N_], H[M_];
int n, w[N_], K, C[N_], Dep[N_], par[N_][20], PPP[N_], Num[N_], Ed[N_], ReNum[N_], cnt;
void DFS(int a, int pp) {
	par[a][0] = pp;
	C[a] = 1;
	for (int i = 0; i < 18; i++)par[a][i + 1] = par[par[a][i]][i];
	for (auto &x : E[a]) {
		if (x != pp) {
			Dep[x] = Dep[a] + 1;
			DFS(x, a);
			C[a] += C[x];
		}
	}
}
void HLD(int a, int pp, int rt) {
	Num[a] = ++cnt;
	ReNum[cnt] = a;
	G[n + cnt].push_back(w[a]);
	PPP[a] = rt;
	int Mx = -1, pv = -1;
	for (auto &x : E[a]) {
		if (x == pp)continue;
		if (Mx < C[x])Mx = C[x], pv = x;
	}
	if (pv != -1) {
		G[n+cnt + 1].push_back(n+cnt);
		HLD(pv, a, rt);
	}
	for (auto &x : E[a]) {
		if (x != pp && x != pv)HLD(x, a, x);
	}
}
int LCA(int a, int b) {
	if (Dep[a] < Dep[b])return LCA(b, a);
	int d = Dep[a] - Dep[b], i;
	for (i = 0; i < 18; i++)if ((d >> i) & 1)a = par[a][i];
	for (i = 17; i >= 0; i--)if (par[a][i] != par[b][i])a = par[a][i], b = par[b][i];
	if (a != b)a = par[a][0];
	return a;
}
void MEdge(int st, int nd, int b, int e, int s, int l) {
	if (s > l)return;
	if (s <= b && e <= l) {
		G[st].push_back(n + n + nd);
		return;
	}
	int m = (b + e) >> 1;
	if (s <= m)MEdge(st, nd * 2, b, m, s, l);
	if (l > m)MEdge(st, nd * 2 + 1, m + 1, e, s, l);
}
void Make_Edge(int st, int a, int p) {
	while (1) {
		if (Dep[PPP[a]] <= Dep[p]) {
			MEdge(st, 1, 1, n, Num[p], Num[a]);
			return;
		}
		G[st].push_back(n+Num[a]);
		a = par[PPP[a]][0];
	}
}
void Build(int nd, int b, int e) {
	if (b == e) {
		G[n + n + nd].push_back(w[ReNum[b]]);
		return;
	}
	int m = (b + e) >> 1;
	G[n + n + nd].push_back(n + n + nd * 2);
	G[n + n + nd].push_back(n + n + nd * 2 + 1);
	Build(nd * 2, b, m);
	Build(nd * 2 + 1, m + 1, e);
}
int ord[M_], SCC[M_], cc, sc, CC[M_];
bool chk[M_], vis[M_];
void DFS1(int a) {
	vis[a] = 1;
	for (auto &x : G[a]) {
		if (!vis[x])DFS1(x);
	}
	ord[++cc] = a;
}
void DFS2(int a) {
	SCC[a] = sc;
	if (a <= K)CC[sc]++;
	for (auto &x : H[a]) {
		if (!SCC[x])DFS2(x);
	}
}
int main() {
	//freopen("input.txt", "r", stdin);
	int i;
	scanf("%d%d", &n,&K);
	for (i = 1; i < n; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		E[a].push_back(b);
		E[b].push_back(a);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &w[i]);
		P[w[i]].push_back(i);
	}
	DFS(1, 0);
	HLD(1, 0, 1);
	Build(1, 1, n);
	for (i = 1; i <= K; i++) {
		int a = P[i][0];
		for (auto &t : P[i])a = LCA(a, t);
		for (auto &t : P[i]) {
			Make_Edge(i, t, a);
		}
	}
	for (i = 1; i < M_; i++) {
		for (auto &t : G[i]) {
			H[t].push_back(i);
		}
	}
	for (i = 1; i < M_; i++) {
		if (!vis[i]) {
			DFS1(i);
		}
	}
	for (i = cc; i >= 1; i--) {
		if (!SCC[ord[i]]) {
			sc++;
			DFS2(ord[i]);
		}
	}
	for (i = 1; i < M_; i++) {
		for (auto &t : G[i]) {
			if (SCC[i] != SCC[t]) {
				chk[SCC[i]] = 1;
			}
		}
	}
	int res = 1e9;
	for (i = 1; i <= sc; i++) {
		if (!chk[i] && CC[i])res = min(res, CC[i]);
	}
	printf("%d\n",res - 1);
}

Compilation message (stderr)

capital_city.cpp: In function 'int main()':
capital_city.cpp:97: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:100: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:105:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &w[i]);
   ~~~~~^~~~~~~~~~~~~

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