oj.uz

Submission #417904

# Submission time Handle Problem Language Result Execution time Memory
417904 2021-06-04T13:32:12 Z nicolaalexandra Joker (BOI20_joker) C++14
0 / 100
 2000 ms 9620 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;

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;

    /// 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--;

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

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

    } else {
        for (opt_mid = min(m,opt_dr); opt_mid >= mid ; 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--;

            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;

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

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

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

        /*if (dp[x] == m+1 || dp[x] > y)
            cout<<"YES\n";
        else cout<<"NO\n";*/
    }


    return 0;
}

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 786 ms 6528 KB Output is correct
4 Correct 1049 ms 9620 KB Output is correct
5 Correct 898 ms 9044 KB Output is correct
6 Correct 806 ms 5892 KB Output is correct
7 Correct 806 ms 6004 KB Output is correct
8 Correct 918 ms 5248 KB Output is correct
9 Correct 927 ms 6600 KB Output is correct
10 Correct 1077 ms 9284 KB Output is correct
11 Correct 903 ms 6440 KB Output is correct
12 Execution timed out 2071 ms 7028 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 22.0

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

Subtask #6
0 / 29.0

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