Submission #573140

#	Time	Username	Problem	Language	Result	Execution time	Memory
573140		tengiz05	Joker (BOI20_joker)	C++17	14 / 100	2075 ms	8264 KiB

Joker

#include <bits/stdc++.h>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m, q;
    std::cin >> n >> m >> q;
    
    std::vector<int> from(m), to(m);
    for (int i = 0; i < m; i++) {
        std::cin >> from[i] >> to[i];
        from[i]--;
        to[i]--;
    }
    
    std::vector<int> p(n), c(n), siz(n, 1);
    std::iota(p.begin(), p.end(), 0);
    
    auto leader = [&](int u) {
        while (u != p[u]) u = p[u];
        return u;
    };
    
    auto color = [&](int u) {
        int x = c[u];
        while (u != p[u]) {
            u = p[u];
            x ^= c[u];
        }
        return x;
    };
    
    int cnt = 0;
    
    std::vector<std::tuple<int, int, int, int>> h;
    
    auto merge = [&](int id) {
        int u = from[id];
        int v = to[id];
        int a = leader(u);
        int b = leader(v);
        h.emplace_back(id, a, b, color(u) == color(v));
        if (a == b) {
            if (color(u) == color(v)) {
                cnt++;
            }
        } else {
            if (siz[a] < siz[b]) {
                std::swap(a, b);
            }
            if (color(u) == color(v)) {
                c[b] ^= 1;
            }
            c[b] ^= c[a];
            siz[a] += siz[b];
            p[b] = a;
        }
        return;
    };
    
    auto unmerge = [&]() {
        auto [id, a, b, col] = h.back();
        h.pop_back();
        if (a == b) {
            if (col) {
                cnt--;
            }
        } else {
            if (siz[a] < siz[b]) {
                std::swap(a, b);
            }
            siz[a] -= siz[b];
            p[b] = b;
        }
    };
    auto rollback = [&](int x) {
        while (x--) {
            assert(!h.empty());
            unmerge();
        }
    };
    
    std::vector<int> opt(m);
    
    for (int i = 0; i < m; i++) {
        int j = m - 1;
        while (cnt == 0 && j >= i) {
            merge(j);
            j--;
        }
        opt[i] = j;
        rollback(m - 1 - j);
        merge(i);
    }
    
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;
        r--;
        
        if (cnt && r <= opt[l]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
    
    return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29