제출 #527919

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
527919		pooyashams	Inside information (BOI21_servers)	C++14	100 / 100	604 ms	51360 KiB

servers

#pragma GCC diagnostic ignored "-Wmisleading-indentation"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cstring>
#include <iomanip>
#include <vector>
#include <bitset>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int maxn = 3e5+10;
const int lgmx = 20;

struct fwt
{
	vector<int> fen;
	int n;
	fwt(){};
	fwt(int _n)
	{
		n = _n+10;
		fen = vector<int>(n, 0);
	}
	inline void add(int r, int x)
	{
		for(r+=3; r < n; r += r&-r)
			fen[r] += x;
	}
	inline int get(int r)
	{
		int out = 0;
		for(r+=3; r > 0; r -= r&-r)
			out += fen[r];
		return out;
	}
	inline int get(int l, int r)
	{
		return get(r-1)-get(l-1);
	}
} fen;

vector<pii> G[maxn];
int type[maxn];
int as[maxn];
int bs[maxn];
int ans[maxn];
vector<int> qrs[maxn];

#define u e.first
#define w e.second

int hight[maxn];
int par[maxn][lgmx];
int wpar[maxn];
int fmfi[maxn];
int fmfd[maxn];

void dfslca(int v, int p, int h, int x)
{
	hight[v] = h;
	wpar[v] = x;
	par[v][0] = p;
	for(int k = 1; k < lgmx; k++)
		par[v][k] = par[par[v][k-1]][k-1];
	for(pii e: G[v])
	{
		if(u == p) continue;
		if(x < w)
		{
			fmfd[u] = fmfd[v];
			fmfi[u] = h-1;
		}
		else // x > w (w != x)
		{
			fmfd[u] = h-1;
			fmfi[u] = fmfi[v];
		}
		dfslca(u, v, h+1, w);
	}
}

inline int getpar(int v, int k)
{
	for( ; k > 0; k -= k&-k)
		v = par[v][__builtin_ctz(k)];
	return v;
}

inline pii lca(int x, int y)
{
	if(hight[x] > hight[y])
		x = getpar(x, hight[x]-hight[y]);
	else
		y = getpar(y, hight[y]-hight[x]);
	if(x == y) return {x, y};
	for(int i = lgmx-1; i >= 0; i--)
	{
		if(par[x][i] != par[y][i])
		{
			x = par[x][i];
			y = par[y][i];
		}
	}
	return {x, y};
}

bool dead[maxn];
int sz[maxn];

int pre(int v, int p)
{
	sz[v] = 1;
	for(pii e: G[v])
		if(!dead[u] and u != p)
			sz[v] += pre(u, v);
	return sz[v];
}

int find_cntrd(int v, int p, int s)
{
	for(pii e: G[v])
		if(!dead[u] and u != p and sz[u]*2 > s)
			return find_cntrd(u, v, s);
	return v;
}

void addans(int v, int p, int x)
{
	for(int i: qrs[v])
		ans[i] += fen.get(i);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w > x))
			addans(u, v, w);
}
void addvrt(int v, int p, int x)
{
	fen.add(x, 1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			addvrt(u, v, w);
}
void clrvrt(int v, int p, int x)
{
	fen.add(x, -1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			clrvrt(u, v, w);
}
void srcadd(int v, int p, int x)
{
	fen.add(x, 1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			srcadd(u, v, w);
}
void srcclr(int v, int p, int x)
{
	fen.add(x, -1);
	for(pii e: G[v])
		if(not (u == p or dead[u] or w < x))
			srcclr(u, v, w);
}
void srcapp(int v, int p, int x, int ix)
{
	for(int i: qrs[v])
		if(i > ix)
			ans[i]++;
	for(pii e: G[v])
		if(not (u == p or dead[u] or w > x))
			srcapp(u, v, w, ix);
}

void dcmps(int v)
{
	v = find_cntrd(v, v, pre(v, v));
	//cerr << "--- " << v << " ---" << endl;
	dead[v] = true;
	for(pii e: G[v])
	{
		if(dead[u]) continue;
		addans(u, v, w);
		addvrt(u, v, w);
	}
	for(pii e: G[v])
		if(!dead[u])
			clrvrt(u, v, w);
	for(pii e: G[v])
		if(!dead[u])
			srcadd(u, v, w);
	for(int i: qrs[v])
		ans[i] += fen.get(i);
	for(pii e: G[v])
		if(!dead[u])
			srcclr(u, v, w);
	for(pii e: G[v])
		if(!dead[u])
			srcapp(u, v, w, w);
	for(pii e: G[v])
		if(!dead[u])
			dcmps(u);
}

int32_t main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,k; cin >> n >> k;
	int q = n+k-1;
	fen = fwt(q);
	for(int i = 0; i < q; i++)
	{
		char c; cin >> c;
		if(c == 'S')
		{
			type[i] = 0;
			cin >> as[i] >> bs[i];
			as[i]--; bs[i]--;
			G[as[i]].push_back({bs[i], i});
			G[bs[i]].push_back({as[i], i});
		}
		else if(c == 'Q')
		{
			type[i] = 1;
			cin >> as[i] >> bs[i];
			as[i]--; bs[i]--;
		}
		else // c == 'C'
		{
			type[i] = 2;
			cin >> as[i];
			as[i]--;
			qrs[as[i]].push_back(i);
		}
	}
	for(int v = 0; v < n; v++)
		sort(G[v].begin(), G[v].end(), [&](pii i, pii j){ return i.second > j.second; });
	fmfi[0] = -1;
	fmfd[0] = -1;
	dfslca(0, 0, 0, 0);
	//for(int i = 0; i < n; i++) cerr << wpar[i] << " "; cerr << endl;
	for(int i = 0; i < q; i++)
	{
		if(type[i] == 1)
		{
			int a = as[i];
			int b = bs[i];
			if(a == b)
			{
				ans[i] = 1;
				continue;
			}
			pii p = lca(a, b);
			int ap = p.first;
			int bp = p.second;
			if(ap == bp)
			{
				if(ap == a)
				{
					int r = getpar(b, hight[b]-hight[a]-1);
					ans[i] = (hight[a] > fmfi[b] and wpar[r] < i);
				}
				else // ap == b
					ans[i] = (hight[b] > fmfd[a] and wpar[a] < i);
			}
			else
			{
				int r = par[ap][0];
				ans[i] = (wpar[a] < i and wpar[ap] > wpar[bp] and hight[r] > max(fmfi[b], fmfd[a]) );
			}
		}
	}
	dcmps(0);
	for(int i = 0; i < q; i++)
	{
		if(type[i] == 1)
		{
			if(ans[i]) cout << "yes" << endl;
			else cout << "no" << endl;
		}
		else if(type[i] == 2)
		{
			cout << ans[i]+1 << endl;
		}
	}
	return 0;
}

• Subtask 1: 2.5 / 2.5
• Subtask 2: 2.5 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 2.5 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 12.5 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 17.5 / 17.5