Submission #921898

#	Time	Username	Problem	Language	Result	Execution time	Memory
921898		gelastropod	Trampoline (info1cup20_trampoline)	C++14	100 / 100	1146 ms	108068 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define in(s, v) (s.lower_bound(v) != s.end() && *s.lower_bound(v) == v)

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

int kances(int k, int x)
{
    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 N, R, C, T, a, b, counter = 0, c, d, x;
    cin >> R >> C >> N;
    adjlist = vector<vector<int>>(N, vector<int>());
    twok = vector<vector<int>>(20, vector<int>(N, -1));
    map<int, set<pair<int, int>>> green;
    set<int> visited;
    vector<pair<int, int>> greens;
    vector<int> subroots;
    for (int i = 0; i < N; i++)
    {
        cin >> a >> b;
        a--, b--;
        if (!in(visited, a))
        {
            visited.insert(a);
            green[a] = set<pair<int, int>>();
        }
        green[a].insert(pair<int, int>(b, counter));
        greens.push_back(pair<int, int>(b, a));
        counter++;
    }
    for (auto i : green)
    {
        for (auto j : i.second)
        {
            if (!in(visited, 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 (!in(visited, 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(d - b - 1, x);
        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