제출 #848353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
848353		MilosMilutinovic	Long Mansion (JOI17_long_mansion)	C++14	0 / 100	1027 ms	61172 KiB

long_mansion

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> c(n);
    for (int i = 0; i < n - 1; i++) {
        cin >> c[i];
        --c[i];
    }
    vector<int> b(n);
    vector<vector<int>> a(n);
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        a[i].resize(b[i]);
        for (int j = 0; j < b[i]; j++) {
            cin >> a[i][j];
            --a[i][j];
        }
    }
    vector<int> par(n);
    iota(par.begin(), par.end(), 0);
    function<int(int)> Get = [&](int x) {
        return par[x] == x ? x : par[x] = Get(par[x]);  
    };
    vector<int> L(n), R(n), myL(n), myR(n);
    vector<vector<int>> alive(n);
    vector<set<int>> keys(n);
    set<int> none, canL, canR, canLR;
    auto CanL = [&](int i) {
        i = Get(i);
        return (L[i] > 0 && keys[i].find(c[L[i] - 1]) != keys[i].end());
    };
    auto CanR = [&](int i) {
        i = Get(i);
        return (R[i] + 1 < n && keys[i].find(c[R[i]]) != keys[i].end());
    };
    for (int i = 0; i < n; i++) {
        L[i] = R[i] = i;
        alive[i].push_back(i);
        for (int j = 0; j < b[i]; j++) {
            keys[i].insert(a[i][j]);
        }
        if (CanL(i) && CanR(i)) {
            canLR.insert(i);
        } else if (CanL(i)) {
            canL.insert(i);
        } else if (CanR(i)) {
            canR.insert(i);
        } else {
            none.insert(i);
        }
    }
    auto Merge = [&](int x, int y) {
        x = Get(x);
        y = Get(y);
        if (x == y) {
            return;
        }
        if (CanL(x) && CanR(x)) {
            canLR.erase(x);
        } else if (CanL(x)) {
            canL.erase(x);
        } else if (CanR(x)) {
            canR.erase(x);
        } else {
            none.erase(x);
        }
        if (CanL(y) && CanR(y)) {
            canLR.erase(y);
        } else if (CanL(y)) {
            canL.erase(y);
        } else if (CanR(y)) {
            canR.erase(y);
        } else {
            none.erase(y);
        }
        for (int i : keys[y]) {
            keys[x].insert(i);
        }
        for (int i : alive[y]) {
            alive[x].push_back(i);
        }
        alive[y].clear();
        L[x] = min(L[x], L[y]);
        R[x] = max(R[x], R[y]);
        par[y] = x;
        if (CanL(x) && CanR(x)) {
            canLR.insert(x);
        } else if (CanL(x)) {
            canL.insert(x);
        } else if (CanR(x)) {
            canR.insert(x);
        } else {
            none.insert(x);
        }
    };
    while (true) {
        if (!none.empty()) {
            auto it = none.begin();
            int c = *it;
            none.erase(it);
            for (int i : alive[c]) {
                myL[i] = L[c];
                myR[i] = R[c];
            }
            alive[c].clear();
            continue;
        }
        if (!canL.empty()) {
            auto it = canL.begin();
            int c = *it;
            Merge(Get(L[c] - 1), c);
            continue;
        }
        if (!canR.empty()) {
            auto it = prev(canR.end());
            int c = *it;
            Merge(c, Get(R[c] + 1));
            continue;
        }
        if (!canLR.empty()) {
            auto it = canLR.begin();
            int c = *it;
            Merge(Get(L[c] - 1), c);
            continue;
        }
        break;
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        --x; --y;
        cout << (myL[x] <= y && y <= myR[x] ? "YES" : "NO") << '\n';
    }
    return 0;
}

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