Submission #1010837

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010837		VMaksimoski008	Joker (BOI20_joker)	C++17	49 / 100	1648 ms	16772 KiB

Joker

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

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,bmi,bmi2,lzcnt,popcnt")

using pii = pair<int, int>;

struct DSU {
    int n, P;
    vector<pii> par;
    vector<int> size, bi;
    vector<pair<int&, int> > st;

    void init(int _n, int _P) {
        n = _n + 1;
        P = _P;
        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;
        
        if(P) {
            auto p2 = find(par[u].first);
            return { p2.first, p2.second ^ p };
        }

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

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

        if(P) st.push_back({ bi[pa.first], bi[pb.first] });
        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);

        if(P) {
            st.push_back({ size[pa.first], size[pa.first] });
            st.push_back({ par[pa.first].first, par[pa.first].first });
            st.push_back({ par[pa.first].second, par[pa.first].second });
        }

        size[pa.first] += size[pb.first];
        par[pb.first] = { pa.first, pa.second ^ pb.second ^ 1 };
        bi[pa.first] &= bi[pb.first];

        return 1;
    }

    void roll(int sz) {
        while(st.size() > sz) {
            st.back().first = st.back().second;
            st.pop_back();
        }
    }

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

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

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

    vector<array<int, 2> > edges(m);
    for(auto &[a, b] : edges) cin >> a >> b;

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

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

            cout << (!ans ? "YES" : "NO") << '\n';
        }
        
        return 0;
    }

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

    vector<bool> ans(q);
    for(int it=0; it<200; it++) {
        if(qus[it].empty()) continue;
        sort(qus[it].rbegin(), qus[it].rend());

        int p = 0, ok = 1;
        DSU dsu; dsu.init(n, 0);
        for(int i=0; i<it; i++) {
            dsu.uni(edges[i][0], edges[i][1]);
            if(!dsu.getBi(edges[i][0])) ok = 0;
        }

        for(int i=m-1; i>=0&&ok; i--) {
            while(p < qus[it].size() && qus[it][p].first == i) {
                ans[qus[it][p].second] = ok;
                p++;
            }

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

    for(int i=0; i<q; i++)
        cout << (!ans[i] ? "YES" : "NO") << '\n';
    return 0;
}

Compilation message (stderr)

Joker.cpp: In member function 'void DSU::roll(int)':
Joker.cpp:63:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |         while(st.size() > sz) {
      |               ~~~~~~~~~~^~~~
Joker.cpp: In function 'int main()':
Joker.cpp:125:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |             while(p < qus[it].size() && qus[it][p].first == i) {
      |                   ~~^~~~~~~~~~~~~~~~

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