Submission #636627

# Submission time Handle Problem Language Result Execution time Memory
636627 2022-08-29T18:13:19 Z ParsaEs Mergers (JOI19_mergers) C++17
0 / 100
13 ms 23764 KB
//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], d1[xn], h[xn], s[xn], z[xn], t, x, y;
bool f[xn << 2], mk[xn], vis[xn], 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), d1[u]++, d1[v]++;
	}
	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]++;
	}
	vector<ii> v1;
	rep(i, 0, n) if(d1[i] < 2) v1.pb(i);
	while(!v1.empty())
	{
		ii v = v1.back();
		v1.pop_back();
		if(mk[v]) continue;
		for(ii u : g[v]) d1[u]--;
		d1[v] = -1, mk[v] = 1;
		if(d[v] > 0)
		{
			ans++;
			continue;
		}
		for(ii u : g[v]) if(d1[u] >= 0 && d1[u] < 2)
		{
			v1.pb(u);
			break;
		}
	}
	ans >>= 1;
	cout << ans << '\n';
	*/
	cout << "0\n";
}

Compilation message

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;
      |         ~~^~~
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Output is correct
2 Incorrect 11 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23764 KB Output isn't correct
2 Halted 0 ms 0 KB -