Submission #417910

#	Time	Username	Problem	Language	Result	Execution time	Memory
417910		nicolaalexandra	Joker (BOI20_joker)	C++14	25 / 100	1056 ms	9588 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 &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 || first){ /// se strica proprietatea de bipartit pana sa ajung la mid
        dp[mid] = m+1;
        opt_mid = m+1;
        if (!first)
            first = mid;

    } 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
• Subtask 2: 0 / 8
• Subtask 3: 25 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29