Submission #417953

#	Time	Username	Problem	Language	Result	Execution time	Memory
417953		nicolaalexandra	Joker (BOI20_joker)	C++14	100 / 100	976 ms	14988 KiB

Joker

#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 = m;

    /// 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
        if (mid == 188)
            mid = 188;
        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;

        if (dp[mid] == 201)
            dp[mid] = 201;
    }

    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;

            break;
        }
    }

    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 > 0){
                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
    n += 2;

    for (i=1;i<=2*n;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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29