Submission #261196

#	Time	Username	Problem	Language	Result	Execution time	Memory
261196		Saboon	Capital City (JOI20_capital_city)	C++14	100 / 100	1570 ms	70772 KiB

capital_city

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;

int n, m;
vector<int> t[maxn], cit[maxn];
int sz[maxn], st[maxn], h[maxn], par[maxn][18], up[maxn], Time = 0, inPlace[maxn];
int Grand[maxn], col[maxn];

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
	for (int i = 17; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = 17; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];
	return par[v][0];
}

int dis(int v, int u){
	return h[v] + h[u] - 2*h[lca(v,u)];
}

int seg[4*maxn], lazy[4*maxn];

void shift(int,int,int);

int get(int id, int L, int R, int l, int r){
	if (r <= L or R <= l or seg[id] == 0)
		return -1;
	if (L+1 == R)
		return L;
	shift(id, L, R);
	int mid = (L + R) >> 1;
	int ret = get(2*id+0, L, mid, l, r);
	if (ret != -1)
		return ret;
	return get(2*id+1, mid, R, l, r);
}

void change(int id, int L, int R, int l, int r, int val){
	if (r <= L or R <= l)
		return;
	if (l <= L and R <= r){
		seg[id] = val;
		lazy[id] = val;
		return;
	}
	shift(id, L, R);
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, l, r, val);
	change(2*id+1, mid, R, l, r, val);
	seg[id] = max(seg[2*id+0], seg[2*id+1]);
}

void shift(int id, int L, int R){
	if (lazy[id] == -1)
		return;
	int mid = (L + R) >> 1;
	change(2*id+0, L, mid, L, mid, lazy[id]);
	change(2*id+1, mid, R, mid, R, lazy[id]);
	lazy[id] = -1;
}

int cmpCount, distinctColor[maxn];
vector<int> cmp[maxn], topol;
bool visited[maxn];

void dfs(int c, bool w){
	visited[c] = 1;
	for (auto it : cit[c]){
		int v = it;
		change(1, 0, n, st[v], st[v]+1, 0);
		while (v != -1 and h[v] > h[Grand[c]]){
			int l = (h[up[v]] >= h[Grand[c]] ? st[up[v]] : st[Grand[c]]), r = st[v]+1;
			int idx = get(1, 0, n, l, r);
			if (idx == -1){
				v = par[up[v]][0];
				continue;
			}
			change(1, 0, n, idx, idx+1, 0);
			if (!visited[col[inPlace[idx]]])
				dfs(col[inPlace[idx]], w);
		}
	}
	if (w == 0)
		topol.push_back(c);
	else{
		for (auto v : cit[c])
			cmp[cmpCount].push_back(v);
		distinctColor[cmpCount] ++;
	}
}

void SCC(){
	change(1, 0, n, 0, n, 1);
	for (int i = 1; i <= m; i++)
		if (!visited[i])
			dfs(i, 0);
	change(1, 0, n, 0, n, 1);
	memset(visited, 0, sizeof visited);
	for (auto i : topol)
		if (!visited[i])
			dfs(i, 1), cmpCount ++;
}

void dfs1(int v, int p = -1){
	par[v][0] = p;
	for (int i = 1; par[v][i-1] != -1 and i < 18; i++)
		par[v][i] = par[par[v][i-1]][i-1];
	st[v] = Time, inPlace[Time++] = v;
	bool bigChild = true;
	for (auto u : t[v]){
		h[u] = h[v] + 1;
		if (bigChild)
			up[u] = up[v];
		else
			up[u] = u;
		bigChild = false;
		dfs1(u, v);
	}
}

int dfssz(int v, int par = -1){
	for (int i = 0; i < t[v].size(); i++)
		if (t[v][i] == par)
			t[v].erase(t[v].begin() + i);
	sz[v] = 1;
	for (auto u : t[v])
		sz[v] += dfssz(u, v);
	sort(t[v].begin(), t[v].end(), [](int a, int b){return sz[a] > sz[b];});
	return sz[v];
}

int main(){
	ios_base::sync_with_stdio(false);
	cin >> n >> m;
	for (int i = 0; i < n-1; i++){
		int v, u;
		cin >> v >> u;
		t[v].push_back(u);
		t[u].push_back(v);
	}
	dfssz(1);
	memset(par, -1, sizeof par);
	up[1] = 1;
	dfs1(1);
	for (int i = 1; i <= n; i++){
		int c;
		cin >> c;
		col[i] = c;
		cit[c].push_back(i);
	}
	int answer = m-1;
	for (int i = 1; i <= m; i++){
		sort(cit[i].begin(), cit[i].end(), [](int a, int b){return st[a] < st[b];});
		Grand[i] = cit[i][0];
		for (auto v : cit[i])
			Grand[i] = lca(Grand[i], v);
		int cnt = 0;
		for (int j = 0; j < cit[i].size(); j++){
			int v = cit[i][j];
			if (j+1 < cit[i].size())
				cnt += dis(v, cit[i][j+1]);
			else
				cnt += dis(v, cit[i][0]);
		}
		cnt = (cnt+2) / 2;
		if (cnt == cit[i].size())
			answer = 0;
	}
	SCC();
	for (int i = 0; i < cmpCount; i++){
		sort(cmp[i].begin(), cmp[i].end(), [](int a, int b){return st[a] < st[b];});
		int cnt = 0;
		for (int j = 0; j < cmp[i].size(); j++){
			int v = cmp[i][j];
			if (j+1 < cmp[i].size())
				cnt += dis(v, cmp[i][j+1]);
			else
				cnt += dis(v, cmp[i][0]);
		}
		cnt = (cnt+2) / 2;
		if (cnt == cmp[i].size())
			answer = min(answer, distinctColor[i]-1);
	}
	cout << answer << endl;
}

Compilation message (stderr)

capital_city.cpp: In function 'int dfssz(int, int)':
capital_city.cpp:130:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < t[v].size(); i++)
                  ~~^~~~~~~~~~~~~
capital_city.cpp: In function 'int main()':
capital_city.cpp:166:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < cit[i].size(); j++){
                   ~~^~~~~~~~~~~~~~~
capital_city.cpp:168:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j+1 < cit[i].size())
        ~~~~^~~~~~~~~~~~~~~
capital_city.cpp:174:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cnt == cit[i].size())
       ~~~~^~~~~~~~~~~~~~~~
capital_city.cpp:181:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0; j < cmp[i].size(); j++){
                   ~~^~~~~~~~~~~~~~~
capital_city.cpp:183:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (j+1 < cmp[i].size())
        ~~~~^~~~~~~~~~~~~~~
capital_city.cpp:189:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (cnt == cmp[i].size())
       ~~~~^~~~~~~~~~~~~~~~

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