Submission #1126044

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126044		heavylightdecomp	Joker (BOI20_joker)	C++20	0 / 100	797 ms	58908 KiB

Joker

#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define i32 signed
#define X first
#define Y second
#define pb push_back
using pii = pair<int,int>;
#define vt vector
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
const int INF = 1e9;
// r+1
// online bipartite dsu
// par[x] = find(par[x])
// vt<int> cc
// merge by size
// walk from the back
// yes[r+1] if the graph is bipartite
//edge case if r = N just say yes
int n,m,q;
vt<pii> edges;
//Yes, n is the number of nodes, correct.
struct merge_op {
    bool before_odd_cycle;
    int u,v;
    vt<int> ccu;
    merge_op() {}
    merge_op(int u, int v, vt<int> ccu, bool before): u(u), v(v), ccu(ccu), before_odd_cycle(before) {}
};
struct Dsu { //ALways on the NOdes
    vt<vt<int>> component_nodes;
    vt<int> parent;
    vt<int> colours; //everything is colour 0 at the start
    vt<merge_op> hist;
    bool yes_odd_cycle = 0;
    int ops = 0;
    int find(int x) {
        if(parent[x] == x) return x;
        return find(parent[x]); //no path compression
    }
    void init() {
        component_nodes.resize(n+5);
        parent.resize(n+5);
        colours.resize(n+5);
        f0r(i,1,n+1) {
            parent[i] = i;
            component_nodes[i].pb(i);
        }
    }
    void go_back_one_operation() {
        assert(sz(hist));
        merge_op cur_op = hist.back();
        hist.pop_back();
        int u = cur_op.u, v = cur_op.v;
        bool before = cur_op.before_odd_cycle;
        if(u != v) {
            vt<int> ccu = cur_op.ccu;
            parent[u] = u;
            f0r(g,0,sz(ccu)) {
                component_nodes[v].pop_back();
                component_nodes[u].pb(ccu[g]);
            }
            yes_odd_cycle = before;
        } else { //we just reset the before
            yes_odd_cycle = before;
        }
    } //validity of colours should be maintained anyways...

    void rollback(int save_point) { //I think the rollback code is correct, we might be missing something though
        while(ops > save_point) {
            go_back_one_operation();
            ops--;
        }
    }
    int save() {
        return ops;
    }
    void merge(int original_u, int original_v) { //Transfer component nodes and stuff
        ops++;
        int u_host = find(original_u), v_host = find(original_v);
        if(u_host == v_host) {
            bool before =yes_odd_cycle;
            if(colours[original_u] == colours[original_v]) { //Yeah buddy this is NOT possible
                yes_odd_cycle = 1;
            } else { //Ignore this edge

            }
            hist.pb(merge_op(u_host, u_host, {}, before));
            //BUG: forgot to return
            return;
        }
        if(sz(component_nodes[u_host]) > sz(component_nodes[v_host])) {
            swap(u_host, v_host);
        }
        hist.pb({u_host, v_host, component_nodes[u_host], yes_odd_cycle});
        parent[u_host] = v_host; //Always need the smaller one
        if(colours[original_u] == colours[original_v]) {
            for(int node : component_nodes[u_host]) {
                colours[node] = !colours[node];
            }
        }
        for(int node : component_nodes[u_host]) {
            component_nodes[v_host].pb(node);
        }
        component_nodes[u_host].clear();
    }
} dsu; //dsu should have nothing to do with our edge array
//DNC find lastl by recursing, then rollbacking (but don't rollback the prefix)
vt<int> last;
void dnc(int need_l, int need_r, int optl, int optr) {
    if(need_l > need_r) return;
    //opt is the splitting point
    //BUG: I think we should not be directly modifying optl
    int mid = (need_l + need_r)/2;
    //BUG:
    int optm = INF, before_all_this = dsu.save();
    for(int e = max(optl, mid); e <= optr; e++) { //assuming [1, need_l) is all filled, answer is definitely in this range
        //makes sure to roll back to [1, need_l]
        dsu.merge(edges[e].X, edges[e].Y);
        if(dsu.yes_odd_cycle) {
            optm = e;
            break;
        }
    }
    bool ret = dsu.yes_odd_cycle;
    if(ret) last[mid] = optm; else last[mid] = INF;
    dsu.rollback(before_all_this);

    if(need_l == need_r) return;
    //it's not n^2 btw
    int before_any_recursion = dsu.save();
    if(not ret) { //
        dnc(need_l, mid-1, optl, optr);
        for(int i = mid+1; i <= need_r; i++) {
            last[i] = INF;
        }

    } else {
        dnc(need_l, mid-1, optl, optm);
        for(int e = optl; e < optm; e++) {
            dsu.merge(edges[e].X, edges[e].Y);
        }
        dnc(mid+1, need_r, optm, optr);
    }
    dsu.rollback(before_any_recursion);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n>>m>>q;
    dsu.init();
    // vt<int> suff (m+5); //Is each suffix of edges starting from i going to have an odd cycle? 
    edges = vt<pii> (2*m+5);
    //BUG: these should have been m instead of n
    f0r(i,1,m+1) { //for i from 1 to n, input the edges
        int u,v; cin>>u>>v;
        edges[i] = {u,v};
    }
    f0r(i,m+1, 2*m+1) { //copy over the edges
        edges[i] = edges[i-m];
    }
   // debug("here i am");
    last.resize(2*m+5); //for the start of each edge....
    dnc(1, 2*m, 1, 2*m);
    //f0r(i,1,2*m+1) { debug((i-1)%m + 1) debug(last[i]); }
    f0r(g,0,q) {
        int l,r;cin >>l>>r;
        int v = last[r+1];
        if(v != INF and v-m <= l) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    
    //Last array should be filled

    // r0f(i,m,1) {
    //     dsu.merge(edges[i].X, edges[i].Y);
    //     suff[i] = dsu.yes_odd_cycle;
    // }
    // f0r(g,0,q) {
    //     int l,r;cin>>l>>r;
    //     //BUG: you still need to check if this is m because m is the limit of r
    //     if(r < m and suff[r+1]) {
    //         cout << "YES\n";
    //     } else {
    //         cout << "NO\n";
    //     }
    // }
}

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