Submission #771860

#	Time	Username	Problem	Language	Result	Execution time	Memory
771860		LittleCube	Inside information (BOI21_servers)	C++17	50 / 100	340 ms	51484 KiB

servers

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define F first
#define S second
using namespace std;

int N, K, pre[120005][20], ts;
pii io[120005], bin[120005][20], e[120005];
piii Q[120005];
vector<pii> E[120005];

const pii no = {-1, -1}, bad = {-2, -2};
pii merge(pii p, pii q)
{
	if (p == no)
		return q;
	if (q == no)
		return p;
	if (p == bad || q == bad)
		return bad;
	if (p.F <= p.S && p.S <= q.F && q.F <= q.S)
		return pii(p.F, q.S);
	if (p.F >= p.S && p.S >= q.F && q.F >= q.S)
		return pii(p.F, q.S);
	return bad;
}

void dfs(int u)
{
	io[u].F = ++ts;
	for (auto [v, w] : E[u])
		if (v != pre[u][0])
		{
			pre[v][0] = u;
			bin[v][0] = pii(w, w);
			for (int p = 0; p + 1 < 20; p++)
				pre[v][p + 1] = pre[pre[v][p]][p],
						   bin[v][p + 1] = merge(bin[v][p], bin[pre[v][p]][p]);
			dfs(v);
		}
	io[u].S = ts;
}

bool ischild(int r, int c)
{
	return io[r].F <= io[c].F && io[c].S <= io[r].S;
}

signed main()
{
	cin >> N >> K;
	for (int i = 0, j = 0; i + j < K + N - 1;)
	{
		char c;
		int a, b = 0;
		cin >> c >> a;
		if (c != 'C')
			cin >> b;

		if (c == 'S')
		{
			j++;
			e[j] = pii(a, b);
			E[a].emplace_back(pii(b, j));
			E[b].emplace_back(pii(a, j));
		}
		else
		{
			i++;
			Q[i] = piii(j, a, b);
		}
	}
	for (int p = 0; p < 20; p++)
		pre[1][p] = 1, bin[1][p] = no;
	dfs(1);

	for (int i = 1; i <= K; i++)
	{
		auto [t, a, b] = Q[i];
		if (b > 0)
		{
			int u = a, v = b;
			pii l = no, r = no;

			for (int p = 19; p >= 0; p--)
				if (!ischild(pre[u][p], v))
					l = merge(l, bin[u][p]), u = pre[u][p];
			if (!ischild(u, v))
				l = merge(l, bin[u][0]), u = pre[u][0];
			
			for (int p = 19; p >= 0; p--)
				if (!ischild(pre[v][p], u))
					r = merge(r, bin[v][p]), v = pre[v][p];
			if (!ischild(v, u))
				r = merge(r, bin[v][0]), v = pre[v][0];

			swap(r.F, r.S);

			// cerr << merge(l, r).F << ' ' << merge(l, r).S << '\n';
			l = merge(merge(pii(t, t), merge(l, r)), pii(0, 0));
			cout << (l != bad ? "yes\n" : "no\n");
		}
	}
}

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