Submission #848379

# Submission time Handle Problem Language Result Execution time Memory
848379 2023-09-12T10:29:24 Z MilosMilutinovic Long Mansion (JOI17_long_mansion) C++17
0 / 100
1036 ms 50188 KB
// 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) {
        if (x != Get(x)) {
            while (true) {
                
            }
        }
        if (y != Get(y)) {
            while (true) {
                
            }
        }
        x = Get(x);
        y = Get(y);
        if (x == y) {
            return;
        }
        if (CanL(x) && CanR(x)) {
            assert(canLR.find(x) != canLR.end());
            canLR.erase(canLR.find(x));
        } else if (CanL(x)) {
            assert(canL.find(x) != canL.end());
            canL.erase(canL.find(x));
        } else if (CanR(x)) {
            assert(canR.find(x) != canR.end());
            canR.erase(canR.find(x));
        } else {
            assert(none.find(x) != none.end());
            none.erase(none.find(x));
        }
        if (CanL(y) && CanR(y)) {
            if (canLR.find(y) != canLR.end()) {
                canLR.erase(canLR.find(y));
            }
        } else if (CanL(y)) {
            if (canL.find(y) != canL.end()) {
                canL.erase(canL.find(y));
            }
        } else if (CanR(y)) {
            if (canR.find(y) != canR.end()) {
                canR.erase(canR.find(y));
            }
        } else {
            if (none.find(y) != none.end()) {
                none.erase(none.find(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(c, Get(L[c] - 1));
            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(c, Get(L[c] - 1));
            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;
}
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 1036 ms 50188 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1116 KB Output isn't correct
2 Halted 0 ms 0 KB -