Submission #258638

#	Time	Username	Problem	Language	Result	Execution time	Memory
258638		Diuven	Joker (BOI20_joker)	C++14	100 / 100	616 ms	18136 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAX = 200010;
struct edge_t { int u, v; };
struct stat_t { int x, p, s, b; };
inline int _min(int a, int b){ return a<b ? a : b; }
inline int _max(int a, int b){ return a>b ? a : b; }


class bipuf {
    bool bip;
    int n, U[MAX*2], S[MAX*2];
    vector<stat_t> hist;
    int find(int x){
        return x==U[x] ? x : find(U[x]);
    }
    stat_t unite(int u, int v){
        u = find(u), v = find(v);
        stat_t bef = {0, 0, 0, bip};
        if(u==v) return bef;
        if(S[u]>S[v]) swap(u, v);
        bef = {u, U[u], S[v], bip};
        U[u] = v; S[v] += S[u];
        return bef;
    }
    void revert(stat_t st){
        bip = st.b;
        int v = st.x;
        if(v==0) return;
        S[U[v]] = st.s;
        U[v] = st.p;
    }
public:
    bipuf(int sz){
        bip = true;
        n = 2*sz+1;
        iota(U+1, U+n+1, 1);
        fill(S+1, S+n+1, 1);
    }
    void add_edge(edge_t e){
        int u = e.u, v = e.v;
        stat_t st1 = unite(u*2, v*2+1);
        stat_t st2 = unite(u*2+1, v*2);
        if(find(u*2) == find(u*2+1) || find(v*2) == find(v*2+1))
            bip = false;
        hist.push_back(st1);
        hist.push_back(st2);
    }
    void pop_edge(){
        stat_t st2 = hist.back(); hist.pop_back();
        stat_t st1 = hist.back(); hist.pop_back();
        revert(st2); revert(st1);
    }
    bool is_bip(){
        return bip;
    }
};

int n, m, q;
edge_t E[MAX];
int lim[MAX];
// lim[l] : using ([1,l] + [lim[l], m]) is bipartite

void solve(int s, int e, int l, int r, bipuf &UF){
    // UF set as [1, s) + (r, m]
    if(s>e) return;
    int mid = (s+e)/2, &pos = lim[mid];
    for(int i=_max(1, s); i<=mid; i++) UF.add_edge(E[i]);
    if(!UF.is_bip()) pos = m+2;
    // [1, mid] + (r, m]

    int bgn = _min(r, m), fin = _max(l, mid+1);
    for(int i=bgn; i>=fin; i--){
        UF.add_edge(E[i]);
        if(UF.is_bip()) pos=i;
    }
    // [1, mid] + [fin, m]
    for(int i=fin; i<=bgn; i++) UF.pop_edge();
    // [1, mid] + (r, m]

    solve(mid+1, e, pos, r, UF);

    for(int i=mid, ss=_max(1, s); i>=ss; i--) UF.pop_edge();
    // [1, s) + (r, m]
    int spl = _min(pos, bgn); 
    for(int i=bgn; i>spl; i--) UF.add_edge(E[i]);
    // [1, s) + (pos, m]

    solve(s, mid-1, l, pos, UF);
    for(int i=spl+1; i<=bgn; i++) UF.pop_edge();
    // [1, s) + (r, m]
}



int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin>>n>>m>>q;

    for(int i=1; i<=m; i++){
        int u, v; cin>>u>>v;
        E[i] = {u, v};
    }
    fill(lim, lim+m+1, m+1);

    static bipuf UF(n);

    solve(0, m, 1, m+1, UF);

    for(int i=1; i<=q; i++){
        int l, r; cin>>l>>r;
        cout<<(lim[l-1] <= r+1 ? "NO" : "YES")<<'\n';
    }

}

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