Submission #531458

#	Time	Username	Problem	Language	Result	Execution time	Memory
531458		pnm1384	Inside information (BOI21_servers)	C++14	100 / 100	632 ms	43496 KiB

servers

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define F first
#define S second

const int N = 24e4 + 20;
vector<pair<int, int>> adj[N];
int ans[N], Cnt[N], gr[N], fir[N], last[N], fen[N];
vector<pair<int, int>> que1[N];
vector<int> que2[N];
bool hide[N], az[N], be[N];
int Cen;
int bads0[N], bads1[N];
int t0, t1;
pair<int, int> verts[N];
int vert_sz = 0;
int is_que[N];

inline void add(int i, int x)
{
	i++;
	for (; i < N; i += i & -i) fen[i] += x;
	return;
}

inline int get(int i)
{
	i++;
	int ans = 0;
	for (; i > 0; i -= i & -i) ans += fen[i];
	return ans;
}

bool compa(pair<int, int> p1, pair<int, int> p2)
{
	return (make_pair(fir[p1.F], p1.S) < make_pair(fir[p2.F], p2.S));
}

void init(int u, int pp = -1)
{
	Cnt[u] = 1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (v != pp && !hide[v])
		{
			init(v, u);
			Cnt[u] += Cnt[v];
		}
	}
	return;
}

int find_cen(int u, int _n, int pp = -1)
{
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (v != pp && !hide[v] && Cnt[v] * 2 > _n) return find_cen(v, _n, u);
	}
	return u;
}

void dfs1(int u, int pp = -1)
{
	if (az[u])
	{
		bads1[t1++] = u;
		verts[vert_sz++] = {u, 1};
	}
	if (be[u])
	{
		bads0[t0++] = u;
		verts[vert_sz++] = {u, 0};
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (hide[v] || v == pp) continue;
		fir[v] = fir[u]; gr[v] = gr[u]; last[v] = w;
		az[v] = be[v] = false;
		if (w < last[u])
		{
			az[v] = az[u];
		}
		if (w > last[u])
		{
			be[v] = be[u];
		}
		dfs1(v, u);
	}
	return;
}

void dfs2(int u, int pp = -1)
{
	for (pair<int, int> ppp : que1[u])
	{
		int v = ppp.F, qq = ppp.S;
		if (v == Cen)
		{
			if (az[u] && fir[u] < qq) ans[qq] = 1;
			continue;
		}
		if (gr[v] == -1) continue;
		if (az[u] && be[v] && fir[u] < fir[v] && last[v] < qq) ans[qq] = 1;
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v] && v != pp) dfs2(v, u);
	}
	return;
}

void dfs3(int u, int pp = -1)
{
	gr[u] = -1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v] && v != pp) dfs3(v, u);
	}
	return;
}

void decompose(int u)
{
	//cout << "            nwklngkneflweknfl nlkwnflnwl nkn    " << gr[0] << '\n';
	init(u);
	u = find_cen(u, Cnt[u]);
	//assert(u == 0);
	//cout << "        " << u + 1 << '\n';
	vert_sz = t0 = t1 = 0;
	Cen = u;
	int tttt = 1;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F, w = ppp.S;
		if (!hide[v]) 
		{
			fir[v] = w; last[v] = w; gr[v] = tttt++; az[v] = be[v] = true;
			dfs1(v, u);
		}
	}
	sort(verts, verts + vert_sz, compa);
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) dfs2(v, u);
	}
	for (pair<int, int> ppp : que1[u])
	{
		int v = ppp.F, qq = ppp.S;
		if (gr[v] == -1) continue;
		if (be[v] && last[v] < qq) ans[qq] = 1;
	}
	for (int i = vert_sz - 1; i > -1; i--)
	{
		int x = verts[i].F, ff = verts[i].S;
		if (ff == 0)
		{
			add(last[x], 1);
			continue;
		}
		for (int qq : que2[x])
		{
			ans[qq] += get(qq - 1);
			if (fir[x] < qq) ans[qq]++;
		}
	}
	for (int qq : que2[u])
	{
		ans[qq] += get(qq - 1);
	}
	for (int i = 0; i < t0; i++)
	{
		add(last[bads0[i]], -1);
	}
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) dfs3(v, u);
	}
	hide[u] = true;
	for (pair<int, int> ppp : adj[u])
	{
		int v = ppp.F;
		if (!hide[v]) decompose(v);
	}
	return;
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	memset(gr, -1, sizeof gr);
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n + k - 1; i++)
	{
		char cc;
		cin >> cc;
		if (cc == 'S')
		{
			int u, v;
			cin >> u >> v;
			u--; v--;
			adj[u].push_back({v, i});
			adj[v].push_back({u, i});
			continue;
		}
		if (cc == 'Q')
		{
			is_que[i] = 1;
			int a, d;
			cin >> a >> d;
			a--; d--;
			if (a == d)
			{
				ans[i] = 1;
				continue;
			}
			que1[d].push_back({a, i});
			continue;
		}
		int u;
		cin >> u;
		is_que[i] = 2;
		u--;
		que2[u].push_back(i);
	}
	decompose(0);
	for (int i = 1; i <= n + k - 1; i++)
	{
		if (is_que[i] == 1)
		{
			if (ans[i] != 0) cout << "yes\n";
			else cout << "no\n";
			continue;
		}
		if (is_que[i] == 2) cout << ans[i] + 1 << '\n';
	}
	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