Submission #636564

#	Time	Username	Problem	Language	Result	Execution time	Memory
636564		ParsaEs	Mergers (JOI19_mergers)	C++17	0 / 100	121 ms	39832 KiB

mergers

//InTheNameOfGOD
//PRS;)
#pragma GCC optimize("unroll-loops", "O2", "Ofast", "O3")
#pragma GCC target("avx2", "sse", "sse2")
#include<bits/stdc++.h>
#define Fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define rep(i, l, r) for(ii i = l; i < r; i++)
#define per(i, l, r) for(ii i = r - 1; i >= l; i--)
#define max(x, y) (x > y ? x : y)
#define pb push_back
#define X first
#define Y second
typedef int ii;
using namespace std;
typedef pair<ii, ii> pi;
constexpr ii xn = 5e5 + 1;
vector<pi> vc[xn];
vector<ii> g[xn];
ii p[xn][19], a[xn], d[xn], h[xn], s[xn], z[xn], t, x, y;
bool f[xn << 2], gt;
void df1(ii v)
{
	rep(i, 1, 19) p[v][i] = p[p[v][i - 1]][i - 1];
	z[v] = 1;
	for(ii u : g[v]) if(p[v][0] != u) p[u][0] = v, h[u] = h[v] + 1, df1(u), z[v] += z[u];
}
void df2(ii v)
{
	ii in = 0, mx = 0;
	for(ii u : g[v]) if(p[v][0] != u && z[u] > mx) mx = z[u], in = u;
	s[v] = t++;
	if(in) a[in] = a[v], df2(in);
	for(ii u : g[v]) if(p[v][0] != u && in != u) a[u] = u, df2(u);
}
inline ii gu(ii v, ii x)
{
	if(x < 0) return 0;
	for(; x; x -= x & -x) v = p[v][__builtin_ctz(x)];
	return v;
}
inline ii lca(ii u, ii v)
{
	if(h[u] > h[v]) swap(u, v);
	v = gu(v, h[v] - h[u]);
	if(u == v) return u;
	per(i, 0, 19) if(p[u][i] != p[v][i]) u = p[u][i], v = p[v][i];
	return p[u][0];
}
void get(ii v, ii l, ii r)
{
	if(x < l || r <= x) return;
	if(f[v] || r - l < 2)
	{
		gt = f[v];
		return;
	}
	ii m = l + r >> 1;
	get(v << 1, l, m), get(v << 1 | 1, m, r);
}
void upd(ii v, ii l, ii r)
{
	if(r <= x || y <= l) return;
	if(x <= l && r <= y)
	{
		f[v] = 1;
		return;
	}
	ii m = l + r >> 1;
	upd(v << 1, l, m), upd(v << 1 | 1, m, r);
}
ii main()
{
	Fast;
	ii n, k, ans = 1;
	cin >> n >> k;
	ii m = n - 1;
	while(m--)
	{
		ii u, v;
		cin >> u >> v;
		g[--u].pb(--v), g[v].pb(u);
	}
	df1(0), df2(0);
	rep(i, 0, n)
	{
		ii b;
		cin >> b;
		vc[--b].pb({s[i], i});
	}
	rep(i, 0, k)
	{
		sort(vc[i].begin(), vc[i].end());
		ii ls = -1;
		for(pi j : vc[i])
		{
			ii v = j.Y;
			if(ls < 0)
			{
				ls = v;
				continue;
			}
			ii u = ls;
			ls = v;
			ii lc = lca(u, v);
			ii w = gu(u, h[u] - h[lc] - 1);
			while(w && s[w] <= s[u]) x = max(s[a[u]], s[w]), y = s[u] + 1, upd(1, 0, n), u = p[a[u]][0];
			w = gu(v, h[v] - h[lc] - 1);
			while(w && s[w] <= s[v]) x = max(s[a[v]], s[w]), y = s[v] + 1, upd(1, 0, n), v = p[a[v]][0];
		}
	}
	rep(i, 1, n)
	{
		x = s[i], gt = 0, get(1, 0, n);
		if(!gt) d[p[i][0]]++, d[i]++;
	}
	rep(i, 0, n) if(d[i] == 1) ans++;
	cout << ans / 2 << '\n';
}

Compilation message (stderr)

mergers.cpp: In function 'void get(ii, ii, ii)':
mergers.cpp:57:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |  ii m = l + r >> 1;
      |         ~~^~~
mergers.cpp: In function 'void upd(ii, ii, ii)':
mergers.cpp:68:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |  ii m = l + r >> 1;
      |         ~~^~~

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