oj.uz

Submission #417913

# Submission time Handle Problem Language Result Execution time Memory
417913 2021-06-04T13:58:01 Z nicolaalexandra Joker (BOI20_joker) C++14
25 / 100
 1095 ms 9692 KB 
#include <bits/stdc++.h>
#define DIM 400010
using namespace std;

int fth[DIM],Size[DIM],dp[DIM];
pair <int,int> mch[DIM];
deque <pair<int,int> > s;
int n,m,q,x,y,i,first;

int get_rad (int x){
    while (fth[x] != x)
        x = fth[x];
    return x;
}

int uneste (int x, int y, int &cnt){
    int radx = get_rad (x), rady = get_rad (y);
    if (radx == rady)
        return 0;

    cnt++;

    if (Size[radx] < Size[rady])
        swap (radx,rady);

    s.push_back(make_pair(radx,rady));
    Size[radx] += Size[rady];
    fth[rady] = radx;

    return 1;
}

void undo(){
    int x = s.back().first, y = s.back().second;
    s.pop_back();
    Size[x] -= Size[y];
    fth[y] = y;
}

void solve (int st, int dr, int opt_st, int opt_dr){
    if (st > dr)
        return;
    int mid = (st+dr)>>1, opt_mid;

    if (mid == 73)
        mid = 73;

    /// adaug tot pana la mid
    int ok = 0;
    int cnt = 0; /// de cate ori fac unirile efective
    for (int i=max(1,st-1);i<mid;i++){
        int x = mch[i].first, y = mch[i].second;

        if (!uneste(x,y,cnt)){
            ok = 1;
            break;
        } else undo(), cnt--;

        if (!uneste(x+n,y+n,cnt)){
            ok = 1;
            break;
        } else undo(), cnt--;

        uneste (x,y+n,cnt);
        uneste (x+n,y,cnt);
    }

    if (ok || first <= mid){ /// se strica proprietatea de bipartit pana sa ajung la mid
        dp[mid] = m+1;
        opt_mid = m+1;
        first = min (first,mid);

    } else {
        for (opt_mid = min(m,opt_dr); opt_mid >= mid && opt_mid > opt_st; opt_mid--){

            /// adaug muchia asta si vad daca se pastreaza propr de bipartit
            int x = mch[opt_mid].first, y = mch[opt_mid].second;

            if (!uneste(x,y,cnt)){
                break;
            } else undo(),cnt--;

            if (!uneste(x+n,y+n,cnt))
                break;
            else undo(), cnt--;

            uneste (x,y+n,cnt); /// muchiile astea vin ca la 2sat
            uneste (x+n,y,cnt);
        }

        dp[mid] = opt_mid;
    }

    /// trb sa construiesc padurile special pt urmatorul apel

    /// dau undo la toate si mai adaug dupa de la opt_mid la opt_dr
    for (int i=1;i<=cnt;i++)
        undo();

    int val = 0;
    for (int i=opt_dr;i>opt_mid;i--){
        int x = mch[i].first, y = mch[i].second;
        uneste (x,y+n,val);
        uneste (x+n,y,val);
    }

    solve (st,mid-1,opt_st,opt_mid);

    for (int i=1;i<=val;i++)
        undo();

    int val2 = 0;
    for (int i=st;i<mid;i++){
        int x = mch[i].first, y = mch[i].second;
        uneste (x,y+n,val2);
        uneste (x+n,y,val2);
    }

    solve (mid+1,dr,opt_mid,opt_dr);

    for (int i=1;i<=val2;i++)
        undo();
}



int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>m>>q;
    for (i=1;i<=m;i++)
        cin>>mch[i].first>>mch[i].second;

    for (i=1;i<=2*n;i++)
        fth[i] = i, Size[i] = 1;
    first = m+1;
    solve (1,m,1,m+1);

    //for (i=1;i<=m;i++)
        //cout<<dp[i]<<"\n";

    for (;q--;){
        cin>>x>>y;

        if (y >= dp[x])
            cout<<"NO\n";
        else cout<<"YES\n";

    }


    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 816 ms 6480 KB Output is correct
4 Correct 1095 ms 9692 KB Output is correct
5 Correct 881 ms 9100 KB Output is correct
6 Correct 799 ms 5812 KB Output is correct
7 Correct 815 ms 5808 KB Output is correct
8 Correct 825 ms 5444 KB Output is correct
9 Correct 871 ms 6548 KB Output is correct
10 Correct 1025 ms 9200 KB Output is correct
11 Correct 833 ms 6520 KB Output is correct
12 Correct 919 ms 8704 KB Output is correct
13 Correct 815 ms 4024 KB Output is correct
14 Correct 861 ms 5288 KB Output is correct
15 Correct 1027 ms 7656 KB Output is correct
16 Correct 1042 ms 9104 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 1 ms 332 KB Output isn't correct
13 Halted 0 ms 0 KB -