제출 #528892

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
528892		ParsaEs	Inside information (BOI21_servers)	C++14	0 / 100	98 ms	25348 KiB

servers

//InTheNameOfGOD
//PRS;)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#define X first
#define Y second
using namespace std;
typedef int ll;
typedef pair<ll,ll> pi;
const ll inf = 2e9, xn = 3e5 + 5;
vector<pi> g[xn], qg[xn];
vector<ll> vc[xn];
ll ans[xn], f[xn], sz[xn], t[xn];
bool vis[xn];
void sdfs(ll v, ll p)
{
    sz[v] = 1;
    for(pi u : g[v]) if(u.X != p && !vis[u.X])
	{
        sdfs(u.X, v);
		sz[v] += sz[u.X];
    }
}
ll gc(ll v, ll p, ll m)
{
    ll mx = 0;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && sz[mx] < sz[u.X]) mx = u.X;
    if((max(sz[mx], m - sz[v]) << 1) <= m) return v;
    return gc(mx, v, m);
}
inline ll get(ll v)
{
	ll ret = 0;
	for(; v; v -= v & -v) ret += f[v];
	return ret;
}
inline void upd(ll v, ll x)
{
    for(; v < xn; v += v & -v) f[v] += x;
}
void idfs(ll v, ll p, ll ls)
{
	upd(ls, 1);
    t[v] = ls;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && ls <= u.Y) idfs(u.X, v, u.Y);
}
void odfs(ll v, ll p, ll ls)
{
	upd(ls, -1);
    t[v] = inf;
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && ls <= u.Y) odfs(u.X, v, u.Y);
}
inline void sa(ll v)
{
    for(ll i : vc[v]) ans[i] += get(i);
    for(pi u : qg[v]) if(t[u.X] <= u.Y) ans[u.Y] = -1;
}
void pdfs(ll v, ll p, ll ls)
{
    sa(v);
    for(pi u : g[v]) if(u.X != p && !vis[u.X] && u.Y <= ls) pdfs(u.X, v, u.Y);
}
void doj(ll v, ll p)
{
    sdfs(v, 0);
	ll cen = gc(v, 0, sz[v]);
    sort(g[cen].begin(), g[cen].end()), idfs(cen, 0, 1), sa(cen);
    for(pi u : g[cen]) if(u.X != p && !vis[u.X])
	{
        odfs(u.X, cen, u.Y);
        upd(t[cen], -1);
		t[cen] = u.Y;
        upd(t[cen], 1), pdfs(u.X, cen, u.Y);
    }
    vis[cen] = 1;
	upd(t[cen], -1);
	t[cen] = inf;
    for(pi u : g[cen]) if(u.X != p && !vis[u.X]) doj(u.X, cen);
}
int main()
{
    ll n, q;
    cin >> n >> q;
	q += n - 1;
    for(ll i = 1; i <= q; i++)
	{
		ll v, u;
		char op;
		cin >> op >> v;
		if(op == 'Q')
		{
			cin >> u;
			ans[i] = -2;
            qg[u].push_back({v, i});
		}
		else if(op == 'C')
		{
			vc[v].push_back(i);
			ans[i] = 0;
		}
        else
		{
			cin >> u;
            g[v].push_back({u, i}), g[u].push_back({v, i});
            ans[i] = -69;
        }
    }
    memset(t, 63, sizeof t), doj(1, 0);
    for(ll i = 1; i <= q; i++) if(ans[i] != -69)
	{
        if(ans[i] >= 0)
		{
			cout << ans[i] << '\n';
			continue;
		}
        if(ans[i] == -2) cout << "no\n";
        else cout << "yes\n";
    }
    return 0;
}

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