Submission #217527

#	Time	Username	Problem	Language	Result	Execution time	Memory
217527		BThero	Capital City (JOI20_capital_city)	C++17	11 / 100	3071 ms	213024 KiB

capital_city

// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define __DBG 1
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (__DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef pair<int, int> pii;

const int MAXN = (int)2e5 + 5;
const int K = 18;

vector<int> adj[MAXN], adj2[MAXN], adj3[MAXN], ord;
int tin[MAXN], tout[MAXN], timer;
int par[MAXN][K];
pii e[MAXN];
int n, m, nn;
int col[MAXN], col2[MAXN], sz[MAXN];
int boss[MAXN];
bool used[MAXN], leaf[MAXN];

void dfs(int v, int pr) {
	par[v][0] = pr;
	
	for (int i = 1; i < K; ++i) {
		par[v][i] = par[par[v][i - 1]][i - 1];
	}
	
	tin[v] = ++timer;
	
	for (int to : adj[v]) {
		if (to != pr) {
			dfs(to, v);
		}
	}
	
	tout[v] = timer;
}

bool isUpper(int a, int b) {
	return tin[a] <= tin[b] && tin[b] <= tout[a];
}

int lca(int a, int b) {
	if (isUpper(a, b)) {
		return a;
	}
	
	if (isUpper(b, a)) {
		return b;
	}
	
	for (int i = K - 1; i >= 0; --i) {
		if (!isUpper(par[a][i], b)) {
			a = par[a][i];
		}
	}
	
	return par[a][0];
}

void dfs2(int v) {
	used[v] = 1;
	
	for (int to : adj2[v]) {
		if (!used[to]) {
			dfs2(to);
		}
	}
	
	ord.pb(v);
}

void dfs3(int v) {
	col2[v] = nn;
	++sz[nn];
	used[v] = 1;
	
	for (int to : adj3[v]) {
		if (!used[to]) {
			dfs3(to);
		}
	}
}

void addEdge(int u, int v) {
	//printf("! %d %d\n", u, v);
	adj2[u].pb(v);
	adj3[v].pb(u);
}

void solve() {
	scanf("%d %d", &n, &m);
	
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		e[i] = mp(u, v);
		adj[u].pb(v);
		adj[v].pb(u);
	}
	
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &col[i]);
	}
	
	dfs(1, 1);
	
	for (int i = 1; i <= n; ++i) {
		if (boss[col[i]] == 0) {
			boss[col[i]] = i;
		}
		else {
			boss[col[i]] = lca(boss[col[i]], i);
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= n; ++j) {
			used[j] = 0;
		}
		
		for (int j = 1; j <= n; ++j) {
			if (col[j] == i) {
				for (int x = j;; x = par[x][0]) {
					used[x] = 1;
					
					if (x == boss[i]) {
						break;
					}
				}
			}
		}
		
		for (int j = 1; j <= n; ++j) {
			if (used[j]) {
				addEdge(i, col[j]);
			}
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		used[i] = 0;
	}
	
	for (int i = 1; i <= m; ++i) {
		if (!used[i]) {
			dfs2(i);
		}
	}
	
	for (int i = 1; i <= m; ++i) {
		used[i] = 0;
	}
	
	for (int i = 1; i <= m; ++i) {
		int v = ord[m - i];
		
		if (!used[v]) {
			++nn;
			dfs3(v);
		}
	}
	
	for (int i = 1; i <= nn; ++i) {
		leaf[i] = 1;
	}
	
	for (int i = 1; i <= m; ++i) {
		for (int to : adj2[i]) {
			int a = col2[i];
			int b = col2[to];
			
			if (a != b) {
				leaf[a] = 0;
			}
		}
	}
	
	int ans = m;
	
	for (int i = 1; i <= nn; ++i) {
		if (leaf[i]) {
			ans = min(ans, sz[i]);
		}
	}
	
	printf("%d\n", ans - 1);
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

Compilation message (stderr)

capital_city.cpp: In function 'void solve()':
capital_city.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &u, &v);
   ~~~~~^~~~~~~~~~~~~~~~~
capital_city.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &col[i]);
   ~~~~~^~~~~~~~~~~~~~~

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