oj.uz

Submission #417944

# Submission time Handle Problem Language Result Execution time Memory
417944 2021-06-04T16:14:05 Z nicolaalexandra Joker (BOI20_joker) C++14
0 / 100
 737 ms 9976 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 radx = get_rad (x), rady = get_rad (y);
    if (radx == rady)
        return 0;

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

int verif (int x, int y){
    int radx = get_rad(x), rady = get_rad(y);
    return radx == rady;
}

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 cnt = 0, ok = 0;
    for (int i=st;i<mid;i++){
        int x = mch[i].first, y = mch[i].second;
        cnt += uneste(x,y+n);
        cnt += uneste(x+n,y);

        if (verif(x,x+n)){ /// am ciclu impar deja
            ok = 1;
            break;
        }
    }

    if (ok){
        dp[mid] = opt_mid = m+1;
    } else {

        /// adaug muchii din dreapta si vad daca se pastreaza propr de bipartit
        for (opt_mid = opt_dr; opt_mid >= opt_st && opt_mid >= mid; opt_mid--){
            int x = mch[opt_mid].first, y = mch[opt_mid].second;
            cnt += uneste(x,y+n);
            cnt += uneste(x+n,y);

            if (verif(x,x+n))
                break;
        }
        dp[mid] = opt_mid;
    }

    while (cnt > 0){
        undo();
        cnt--;
    }

    /// acum trb sa refac padurile a.i. sa se potriveasca pt intervalele urmatoare

    ok = 0;
    for (int i=opt_mid+1;i<=opt_dr;i++){
        int x = mch[i].first, y = mch[i].second;
        cnt += uneste(x,y+n);
        cnt += uneste(x+n,y);

        if (verif(x,x+n)){
            ok = 1;
            while (cnt > 0){
                undo();
                cnt--;
            }
            for (int j=st;j<mid;j++)
                dp[j] = m+1;
        }
    }

    if (!ok){
        solve (st,mid-1,opt_st,opt_mid);


        /// iar undo
        while (cnt > 0){
            undo();
            cnt--;
        }
    }
    /// reconstructie

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

        if (verif(x,x+n)){
            ok = 1;
            while (cnt){
                undo();
                cnt--;
            }

            for (int j=mid+1;j<=dr;j++)
                dp[j] = m+1;

            break;
        }
    }

    if (!ok){
        solve (mid+1,dr,opt_mid,opt_dr);
        while (cnt > 0){
            undo();
            cnt--;
        }
    }

}



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;

    mch[m+1] = make_pair(n+1,n+2); /// nu ma intereseaza asta

    for (i=1;i<=2*n+4;i++)
        fth[i] = i, Size[i] = 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 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 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 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 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 1 ms 204 KB Output is correct
3 Correct 737 ms 6512 KB Output is correct
4 Incorrect 732 ms 9976 KB Output isn't correct
5 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 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 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 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 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 1 ms 204 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 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 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 296 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Incorrect 1 ms 296 KB Output isn't correct
16 Halted 0 ms 0 KB -