oj.uz

Submission #258614

# Submission time Handle Problem Language Result Execution time Memory
258614 2020-08-06T08:46:45 Z Diuven Joker (BOI20_joker) C++14
0 / 100
 2000 ms 11760 KB 
#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, c, rd, 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 uf_t {
    int n, U[MAX], C[MAX], rk[MAX];
    vector<stat_t> hist;
    bool bip;
    int find(int x){
        return x == U[x] ? x : find(U[x]);
    }
    stat_t unite(int x, int y){
        stat_t bef = {0, 0, 0, 0, bip};
        int u = find(x), a = C[x];
        int v = find(y), b = C[y];
        if(u==v){
            if(a==b) bip = false;
            return bef;
        }
        if(rk[u]<rk[v]) swap(u,v);
        bef = {v, U[v], C[v], (rk[u]==rk[v]), bip};
        U[v]=u; C[v]=a^b^1; rk[u] += (rk[u]==rk[v]);
        return bef;
    }
public:
    uf_t(int sz){
        n = sz; bip = true;
        iota(U, U+n+1, 0);
        fill(C, C+n+1, 0);
        fill(rk, rk+n+1, 1);
    }
    void add_edge(edge_t e){
        stat_t now = unite(e.v, e.u);
        hist.push_back(now);
    }
    void pop_edge(){
        stat_t now = hist.back(); hist.pop_back();
        bip = now.b;
        int v = now.x;
        if(v==0) return;
        rk[U[v]] -= now.rd;
        U[v] = now.p; C[v] = now.c;
    }
    bool is_bip(){
        return bip;
    }
};

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

void solve(int s, int e, int l, int r, uf_t &UF){
    // UF set as [1, s) + (r, m]
    if(e>s) return;
    int mid = (s+e)/2, &p = pos[mid];
    for(int i=_max(1, s); i<=mid; i++)
        UF.add_edge(E[i]);
    // [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()) p=i;
    }
    int sto = _min(bgn, p);
    // [1, mid] + [fin, m]
    for(int i=fin; i<=sto; i++)
        UF.pop_edge();
    // [1, mid] + (sto, m]

    solve(s, mid-1, l, p, UF);
    // set UF
    solve(mid+1, e, p, r, UF);
}



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(pos, pos+m+1, m+2);

    static uf_t UF(n);

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

    for(int i=1; i<=q; i++){
        int l, r; cin>>l>>r;
        for(int j=1; j<l; j++)
            UF.add_edge(E[j]);
        for(int j=m; j>r; j--)
            UF.add_edge(E[j]);
        cout<<(UF.is_bip() ? "NO" : "YES")<<'\n';
        for(int j=1; j<l; j++)
            UF.pop_edge();
        for(int j=m; j>r; j--)
            UF.pop_edge();
//        cout<<(pos[l-1] <= r+1 ? "NO" : "YES")<<'\n';
    }

}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Execution timed out 2074 ms 11760 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -