Submission #529362

#	Time	Username	Problem	Language	Result	Execution time	Memory
529362		getac	Inside information (BOI21_servers)	C++14	100 / 100	396 ms	41952 KiB

servers

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef int ll;
typedef pair<ll, ll> pi;
const ll inf = 1e9 + 7, xn = 3e5 + 9;
vector<pi> g[xn], qg[xn];
vector<ll> cnt[xn];
ll ans[xn], f[xn], sz[xn], ti[xn];
bool vis[xn];
void dfs1(ll v, ll p)
{
	sz[v] = 1;
	for(pi u : g[v]) if(u.Y != p && !vis[u.Y])
	{
		dfs1(u.Y, v);
		sz[v] += sz[u.Y];
	}
}
ll dojob(ll v, ll p, ll m)
{
	ll mx = 0;
	for(pi u : g[v]) if(u.Y != p && !vis[u.Y] && sz[mx] < sz[u.Y]) mx = u.Y;
	if(max(m - sz[v], sz[mx]) * 2 <= m) return v;
	return dojob(mx, v, m);
}
inline ll get(ll x)
{
	ll ret = 0;
	while(x > 0) ret += f[x], x -= (x & -x);
	return ret;
}
inline void upd(ll x, ll y)
{
	while(x < xn) f[x] += y, x += (x & -x);
}
void dfs2(ll v, ll p, ll ls)
{
	ti[v] = ls;
	upd(ls, 1);
	for(pi u : g[v]) if(u.Y != p && !vis[u.Y] && ls <= u.X) dfs2(u.Y, v, u.X);
}
void dfs3(ll v, ll p, ll ls)
{
	ti[v] = inf;
	upd(ls, -1);
	for(pi u : g[v]) if(u.Y != p && !vis[u.Y] && ls <= u.X) dfs3(u.Y, v, u.X);
}
inline void pans(ll x)
{
	for(ll i : cnt[x]) ans[i] += get(i);
	for(pi i : qg[x]) if(ti[i.Y] <= i.X) ans[i.X] = -1;
}
void dfs4(ll v, ll p, ll ls)
{
	pans(v);
	for(pi u : g[v]) if(u.Y != p && !vis[u.Y] && u.X <= ls) dfs4(u.Y, v, u.X);
}
void solve(ll v, ll p)
{
	dfs1(v, 0);
	ll cen = dojob(v, 0, sz[v]);
	sort(g[cen].begin(), g[cen].end());
	dfs2(cen, 0, 1), pans(cen);
	for(pi u : g[cen]) if(u.Y != p && !vis[u.Y])
	{
		dfs3(u.Y, cen, u.X), upd(ti[cen], -1);
		ti[cen] = u.X;
		upd(ti[cen], 1), dfs4(u.Y, cen, u.X);
	}
	vis[cen] = 1;
	upd(ti[cen], -1);
	ti[cen] = inf;
	for(pi u : g[cen]) if(u.Y != p && !vis[u.Y]) solve(u.Y, cen);
}
int main()
{
	ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
	ll n, q;
	cin >> n >> q;
	q += n, sz[0] = 0;
	for(ll i = 1; i < q; i++)
	{
		ll x, y;
		char c;
		cin >> c;
		if(c == 'S')
		{
			cin >> x >> y;
			g[x].push_back({i, y}), g[y].push_back({i, x});
			ans[i] = -3;
		}
		else if(c == 'C')
		{
			cin >> x;
			cnt[x].push_back(i);
			ans[i] = 0;
		}
		else
		{
			cin >> x >> y;
			qg[y].push_back({i, x});
			ans[i] = -2;
		}
	}
	for(ll i = 0; i < n + 2; i++) ti[i] = inf;
	solve(1, 0);
	for(ll i = 1; i < q; i++)
	{
		if(ans[i] == -3) continue;
		if(ans[i] >= 0) cout << ans[i] << "\n";
		else
		{
			if(ans[i] == -2) cout << "no";
			else cout << "yes";
			cout << "\n";
		}
	}
}

• 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