Submission #1211446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211446		VMaksimoski008	Long Mansion (JOI17_long_mansion)	C++20	100 / 100	336 ms	54960 KiB

long_mansion

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n; cin >> n;
    
    // c[i] stores the label of edge between node i and i+1 (1-based)
    vector<int> c(n);
    for(int i = 1; i < n; i++) {
        cin >> c[i];
        --c[i]; // make it 0-based
    }

    vector<set<int>> pos(n); // pos[label] = set of nodes that support this label
    for(int i = 1; i <= n; i++) {
        int k; cin >> k;
        while(k--) {
            int x; cin >> x;
            --x; // make label 0-based
            pos[x].insert(i);
        }
    }

    auto in = [&](int l, int r, int x) {
        auto it = pos[x].lower_bound(l);
        return it != pos[x].end() && *it <= r;
    };

    vector<int> lp(n + 1), rp(n + 1);
    for(int i = 1; i <= n; i++) {
        lp[i] = rp[i] = i;
        while(true) {
            if(lp[i] > 1 && in(lp[i], rp[i], c[lp[i] - 1])) {
                rp[i] = max(rp[i], rp[lp[i] - 1]);
                lp[i] = lp[lp[i] - 1];
            } else if(rp[i] < n && in(lp[i], rp[i], c[rp[i]])) {
                rp[i]++;
            } else break;
        }
    }

    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        cout << (lp[x] <= y && y <= rp[x] ? "YES" : "NO") << '\n';
    }

    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75