Submission #922130

#	Time	Username	Problem	Language	Result	Execution time	Memory
922130		gelastropod	Trampoline (info1cup20_trampoline)	C++14	100 / 100	1165 ms	108760 KiB

trampoline

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

vector<vector<int>> adjlist, twok;
void dfs(int x, int p)
{
	for (int i = 0; i < 19; i++)
	{
		if (twok[i][x] == -1) break;
		twok[i + 1][x] = twok[i][twok[i][x]];
	}
	for (int i : adjlist[x])
	{
		if (i == p) continue;
		twok[0][i] = x;
		dfs(i, x);
	}
}

int kances(int x, int k)
{
	for (int i = 0; i < 20; i++)
	{
		if (x == -1) break;
		if (k & (1LL << i)) x = twok[i][x];
	}
	return x;
}

signed main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int R, C, N, T, a, b, c, d, count = 0, x;
	cin >> R >> C >> N;
	adjlist = vector<vector<int>>(N, vector<int>());
	twok = vector<vector<int>>(20, vector<int>(N, -1));
	set<int> visited;
	map<int, set<pair<int, int>>> green;
	vector<pair<int, int>> greens;
	vector<int> subroots;
	for (int i = 0; i < N; i++)
	{
		cin >> a >> b;
		a--, b--;
		swap(a, b);
		if (visited.lower_bound(b) == visited.end() || *visited.lower_bound(b) != b)
		{
			visited.insert(b);
			green[b] = set<pair<int, int>>();
		}
		green[b].insert(pair<int, int>(a, count));
		greens.push_back(pair<int, int>(a, b));
		count++;
	}
	for (auto i : green)
	{
		for (auto j : i.second)
		{
			if (visited.lower_bound(i.first + 1) == visited.end() || *visited.lower_bound(i.first + 1) != i.first + 1)
			{
				subroots.push_back(j.second);
				continue;
			}
			if (green[i.first + 1].lower_bound(pair<int, int>(j.first, 0)) == green[i.first + 1].end())
			{
				subroots.push_back(j.second);
				continue;
			}
			x = green[i.first + 1].lower_bound(pair<int, int>(j.first, 0))->second;
			adjlist[j.second].push_back(x);
			adjlist[x].push_back(j.second);
		}
	}
	for (int i : subroots) dfs(i, -1);
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		cin >> a >> b >> c >> d;
		a--, b--, c--, d--;
		swap(a, b);
		swap(c, d);
		if (a > c || b > d)
		{
			cout << "No\n";
			continue;
		}
		if (b == d)
		{
			cout << "Yes\n";
			continue;
		}
		if (visited.lower_bound(b) == visited.end() || *visited.lower_bound(b) != b)
		{
			cout << "No\n";
			continue;
		}
		if (green[b].lower_bound(pair<int, int>(a, 0)) == green[b].end())
		{
			cout << "No\n";
			continue;
		}
		x = green[b].lower_bound(pair<int, int>(a, 0))->second;
		x = kances(x, d - b - 1);
		if (x == -1)
		{
			cout << "No\n";
			continue;
		}
		cout << (greens[x].first <= c ? "Yes\n" : "No\n");
	}
}

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27