Submission #1010966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010966		VMaksimoski008	Joker (BOI20_joker)	C++17	14 / 100	2083 ms	143136 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;
    vector<pii> par;
    vector<int> size, bi;
 
    void init(int _n) {
        n = _n + 1;
        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) {
        pii 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]; }
};

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+1);
    for(int i=1; i<=m; i++) cin >> edges[i][0] >> edges[i][1];

    vector<int> L(m+1), R(m+1, m), ANS(m+1, m+1);
    for(int i=1; i<=m; i++) L[i] = i;

    bool changed = 1;
    while(changed) {
        changed = 0;

        stack<int> to_change[m+1];
        for(int i=m; i>=1; i--)
            if(L[i] <= R[i]) to_change[(L[i] + R[i]) / 2].push(i);

        for(int i=1; i<=m; i++) {
            if(to_change[i].empty()) continue;
            changed = 1;

            DSU dsu; dsu.init(n);
            int ok = 1;
            for(int j=i+1; j<=m; j++) {
                dsu.uni(edges[j][0], edges[j][1]);
                // cout << edges[j][0] << " - " << edges[j][1] << '\n';
                if(!dsu.getBi(edges[j][0])) ok = 0;
            }

            // cout << i << ": " << ok << '\n';

            for(int j=1; j<=i; j++) {
                if(!to_change[i].empty() && to_change[i].top() == j) {
                    // cerr << i << " " << j << '\n';
                    if(ok) ANS[j] = i, R[j] = i - 1;
                    else L[j] = i + 1;
                    to_change[i].pop();
                }

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

    // for(int i=1; i<=n; i++) cout << i << ": " << ANS[i] << '\n';

    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << (r >= ANS[l] ? "NO" : "YES") << '\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