oj.uz

Submission #417880

# Submission time Handle Problem Language Result Execution time Memory
417880 2021-06-04T12:51:58 Z nicolaalexandra Joker (BOI20_joker) C++14
25 / 100
 1031 ms 13272 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=st;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;

    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 (dp[x] == m+1 || dp[x] > y)
            cout<<"YES\n";
        else cout<<"NO\n";
    }


    return 0;
}

Compilation message

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:43:27: warning: 'opt_mid' may be used uninitialized in this function [-Wmaybe-uninitialized]
   43 |     int mid = (st+dr)>>1, opt_mid;
      |                           ^~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 292 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 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 292 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 786 ms 10464 KB Output is correct
4 Correct 1020 ms 13168 KB Output is correct
5 Correct 819 ms 13272 KB Output is correct
6 Correct 791 ms 10560 KB Output is correct
7 Correct 814 ms 10520 KB Output is correct
8 Correct 821 ms 8728 KB Output is correct
9 Correct 877 ms 9892 KB Output is correct
10 Correct 1031 ms 12824 KB Output is correct
11 Correct 818 ms 10476 KB Output is correct
12 Correct 925 ms 12796 KB Output is correct
13 Correct 752 ms 7760 KB Output is correct
14 Correct 819 ms 9184 KB Output is correct
15 Correct 1002 ms 11632 KB Output is correct
16 Correct 1016 ms 13180 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 292 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 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 292 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 332 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Incorrect 1 ms 292 KB Output isn't correct
5 Halted 0 ms 0 KB -