Submission #1014666

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014666		MODDI	Joker (BOI20_joker)	C++14	49 / 100	2065 ms	24524 KiB

Joker

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")

using pii = pair<int, int>;

struct DSU {
    int n;
    vector<pii> par;
    vector<int> size, bi;

    DSU(int _n) {
        n = _n;
        par.resize(n+1);
        size.resize(n+1, 1);
        bi.resize(n+1, 1);
        for(int i=1; i<=n; i++) par[i] = { i, 0 };
    }

    pii find(int u) {
        if(u == par[u].first) return par[u];
        int p = par[u].second;
        par[u] = find(par[u].first);
        par[u].second ^= p;
        return par[u];
    }

    bool uni(int a, int b) {
        auto pa = find(a), pb = find(b);

        if(pa.first == pb.first) {
            if(pa.second == pb.second) bi[pa.first] = 0;
            return 0;
        }

        if(size[pa.first] < size[pb.first]) swap(pa, pb);
        size[pa.first] += size[pb.first];
        par[pb.first] = { pa.first, pa.second ^ pb.second ^ 1 };
        bi[pa.first] &= bi[pb.first];

        return 1;
    }

    int getBi(int u) { return bi[find(u).first]; }

    void reset() {
        for(int i=1; i<=n; i++) {
            par[i] = { i, 0 };
            size[i] = 1;
            bi[i] = 1;
        }
    }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    vector<array<int, 2> > edges(m+1);
    for(int i=1; i<=m; i++) cin >> edges[i][0] >> edges[i][1];

    if(n <= 2000 && m <= 2000 && q <= 2000) {
        while(q--) {
            int l, r;
            cin >> l >> r;

            DSU dsu(n);
            int bi = 1;
            for(int i=1; i<=m; i++) {
                if(l <= i && i <= r) continue;
                dsu.uni(edges[i][0], edges[i][1]);
                if(!dsu.getBi(edges[i][0])) {
                    bi = 0;
                    break;
                }
            }

            cout << (bi ? "NO" : "YES") << '\n';
        }

        return 0;
    }

    int mx = 0;
    vector<int> ans(q);
    vector<int> qus[m+1];
    vector<pii> qus2[m+1];
    for(int i=0; i<q; i++) {
        int l, r;
        cin >> l >> r;
        mx = max(mx, l);
        qus[r].push_back(i);
        qus2[l].push_back({ r, i });
    }

    if(mx == 1) {
        DSU dsu(n);
        int bi = 1;
        for(int i=m; i>=1; i--) {
            for(int &id : qus[i]) ans[id] = bi;
            dsu.uni(edges[i][0], edges[i][1]);
            if(!dsu.getBi(edges[i][0])) bi = 0;
        }

        for(int &x : ans) cout << (x ? "NO" : "YES") << '\n';
        return 0;
    }

    int bi2=1;
    DSU dsu(n);
    for(int i=1; i<=mx; i++) {
        if(qus2[i].size() == 0) continue;
        if(bi2 == 0) continue;

        sort(qus2[i].begin(), qus2[i].end());
        int bi = 1, p = qus2[i].size() - 1;
        dsu.reset();

        for(int j=1; j<i&&bi2; j++) {
            dsu.uni(edges[j][0], edges[j][1]);
            if(!dsu.getBi(edges[j][0])) {
                bi = 0;
                bi2 = 0;
                break;
            }
        }

        if(!bi2) bi = 0;
        for(int j=m; j>=i&&bi; j--) {
            while(p >= 0 && qus2[i][p].first == j) {
                ans[qus2[i][p].second] = bi;
                p--;
            }

            dsu.uni(edges[j][0], edges[j][1]);
            if(!dsu.getBi(edges[j][0])) bi = 0;
        }

    }

    for(int &x : ans) cout << (x ? "NO" : "YES") << '\n';
    return 0;
}

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