Submission #573142

#	Time	Username	Problem	Language	Result	Execution time	Memory
573142		tengiz05	Joker (BOI20_joker)	C++17	100 / 100	342 ms	14716 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);
    
    std::function<void(int, int, int, int)> dfs = [&](int l, int r, int optl, int optr) {
        if (l > r)
            return;
        int m = (l + r) / 2;
        
        for (int i = l; i < m; i++) {
            merge(i);
        }
        
        opt[m] = optr;
        while (cnt == 0 && opt[m] >= optl) {
            merge(opt[m]);
            opt[m]--;
        }
        
        rollback(optr - opt[m]);
        merge(m);
        dfs(m + 1, r, opt[m], optr);
        rollback(m - l + 1);
        
        for (int i = opt[m] + 1; i <= optr; i++) {
            merge(i);
        }
        dfs(l, m - 1, optl, opt[m]);
        rollback(optr - opt[m]);
    };
    
    dfs(0, m - 1, 0, m - 1);
    
    while (q--) {
        int l, r;
        std::cin >> l >> r;
        l--;
        r--;
        
        if (r <= opt[l]) {
            std::cout << "YES\n";
        } else {
            std::cout << "NO\n";
        }
    }
    
    return 0;
}

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