Submission #113893

#	Time	Username	Problem	Language	Result	Execution time	Memory
113893		Mamnoon_Siam	Mergers (JOI19_mergers)	C++17	100 / 100	1925 ms	154336 KiB

mergers

#include <bits/stdc++.h>
using namespace std;

const int maxn = 5e5 + 5;

int n, k;
int dp[20][maxn];
int where[maxn];
int tym = 0;
vector<int> g[maxn], state[maxn];
int s[maxn];
int lvl[maxn];
int p[maxn], sz[maxn];
using ii = pair<int, int>;
vector<ii> bridges;
int cnt[maxn];

int find(int u) {
	return p[u] == u ? u : p[u] = find(p[u]);
}
void unite(int u, int v) {
	u = find(u);
	v = find(v);
	if(u == v) return;
	if(sz[u] > sz[v]) swap(u, v);
	sz[v] += sz[u];
	p[u] = v;
}

void dfs(int u, int par) {
	for(int v : g[u]) if(v != par) {
		dfs(v, u);
		if(s[v]) unite(u, v);
		else bridges.emplace_back(u, v);
		s[u] += s[v];
	}
}

void dfs0(int u, int par) {
	lvl[u] = par + 1 ? lvl[par] + 1 : 0;
	where[u] = ++ tym;
	dp[0][u] = par;
	for(int i = 1; i <= 19; i++) {
		int mid = dp[i - 1][u];
		if(mid != -1) dp[i][u] = dp[i - 1][mid];
	}
	for(int v : g[u]) if(v != par) {
		dfs0(v, u);
	}
}

int __lca(int u, int v) {
	if(lvl[u] > lvl[v]) swap(u, v);
	int d = lvl[v] - lvl[u];
	for(int i = 19; i >= 0; i--) if(d >> i & 1) {
		v = dp[i][v];
	}
	if(u == v) return u;
	for(int i = 19; i >= 0; i--) {
		if(dp[i][u] != dp[i][v]) {
			u = dp[i][u];
			v = dp[i][v];
		}
	}
	return dp[0][u];
}

int main(int argc, char const *argv[])
{
	// freopen("in", "r", stdin);
	memset(dp, -1, sizeof dp);
	cin >> n >> k;
	for(int i = 1; i < n; i++) {
		int u, v; cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
	for(int i = 1; i <= n; i++) {
		int x; cin >> x;
		state[x].emplace_back(i);
	}
	dfs0(1, -1);
	for(int i = 1; i <= k; i++) {
		sort(state[i].begin(), state[i].end(), [&](int x, int y){ return where[x] < where[y]; });
		for(int j = 1; j < state[i].size(); j++) {
			int u = state[i][j - 1], v = state[i][j];
			s[u]++, s[v]++, ----s[__lca(u, v)];
		}
	}
	for(int i = 1; i <= n; i++){
		p[i] = i, sz[i] = 1;
	}
	dfs(1, -1);
	vector<int> tmp;
	for(ii e : bridges) {
		int u = e.first;
		int v = e.second;
		u = find(u);
		v = find(v);
		cnt[u]++;
		cnt[v]++;
		tmp.emplace_back(u);
		tmp.emplace_back(v);
	}
	sort(tmp.begin(), tmp.end());
	tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
	int ans = 0;
	for(int u : tmp) {
		if(cnt[u] == 1) ans++;
	}
	ans = (ans + 1) / 2;
	cout << ans << endl;
	return 0;
}

Compilation message (stderr)

mergers.cpp: In function 'int main(int, const char**)':
mergers.cpp:85:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 1; j < state[i].size(); j++) {
                  ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 24 / 24
• Subtask 3: 14 / 14
• Subtask 4: 22 / 22
• Subtask 5: 30 / 30