oj.uz

답안 #414447

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
414447 2021-05-30T12:43:41 Z Ruxandra985 Joker (BOI20_joker) C++14
0 / 100
 2000 ms 24356 KB 
#include <bits/stdc++.h>
#define DIMN 400010
using namespace std;
int tt[DIMN];
int sz[DIMN] , opt[DIMN];
int n , m;
pair <int , int> mch[DIMN];
vector <pair <int , int> > s;
int root (int x){
    while (tt[x] != x)
        x = tt[x];
    return x;
}

void unite (int x, int y){
    int radx = root(x), rady = root(y);

    //printf ("add %d %d\n" , x , y);

    if (sz[radx] < sz[rady])
        swap (radx,rady);

    s.push_back(make_pair(radx,rady)); /// stiva pt undo
    sz[radx] += sz[rady];
    tt[rady] = radx;
}

void undo (){
    int x = s.back().first, y = s.back().second;
    s.pop_back();

    //printf ("undo\n");
    sz[x] -= sz[y];
    tt[y] = y;
}

void solve (int st , int dr , int l , int r , int needs){
    int mid = (st + dr)/2 , i , poz , x , y , m2;

    if (needs){
        for (i = dr ; i >= mid ; i--){
            x = mch[i].first;
            y = mch[i].second;
            unite (x , y + n);
            unite (y , x + n);
        }
    }

    l = max(l , 1);

    poz = 0;
    for (i = l ; i <= r && i < mid ; i++){

        x = mch[i].first;
        y = mch[i].second;

        if (root(x) == root(y) || root(y + n) == root(x + n)){
            break;
        }

        unite (x , y + n);

        unite (y , x + n);

        poz = i;

    }

    opt[mid] = poz;

    for (i = l ; i <= poz ; i++){
        undo();
        undo();
    }

    if (st <= mid - 1)
        solve (st , mid - 1 , l , poz , 1);

    if (mid + 1 <= dr){
        m2 = (dr + mid + 1) / 2;
        for (i = mid ; i <= dr; i++){
            undo();
            undo();
        }

        for (i = l ; i < poz ; i++){
            x = mch[i].first;
            y = mch[i].second;
            unite (x , y + n);
            unite (y , x + n);

        }

        solve(mid + 1 , dr , poz , r , 1);
    }

    /// convine sa te duci mai intai in dreapta, pastrezi tot ce ai adaugat


    if (st == dr){
        undo();
        undo();
    }

}

int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int q , i , x , y , poz , j , l , r;
    fscanf (fin,"%d%d%d",&n,&m,&q);
    for (i = 1 ; i <= m ; i++){
        fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
    }

    /// opt se calculeaza intre 1 si M + 1

    for (i = 1 ; i <= 2 * n ; i++){
        tt[i] = i;
        sz[i] = 1;
    }


    for (i = m ; i ; i--){

        x = mch[i].first;
        y = mch[i].second;

        if (root(x) == root(y) || root(y + n) == root(x + n)){
            break;
        }

        unite (x , y + n);

        unite (y , x + n);
    }
    poz = i + 1;
    for (j = i + 1 ; j <= m ; j++){
        undo();
        undo();
    }

    int where = poz;
    solve (poz , m , 1 , m , 1); /// te asiguri ca dreapta nu cauzeaza ciclu impar
    //printf ("-----------------\n");

    for (i = 1 ; i <= m ; i++){
        x = mch[i].first;
        y = mch[i].second;

        if (root(x) == root(y) || root(y + n) == root(x + n)){
            break;
        }

        unite (x , y + n);

        unite (y , x + n);
    }

    poz = i - 1;
    opt[m + 1] = poz;
    for (j = i - 1 ; j ; j--){
        undo();
        undo();
    }

    for (;q;q--){
        fscanf (fin,"%d%d",&l,&r);
        if (opt[r + 1] >= l - 1 && r + 1 >= where)
            fprintf (fout,"NO\n");
        else fprintf (fout,"YES\n");
    }
    return 0;
}

Compilation message

Joker.cpp: In function 'void solve(int, int, int, int, int)':
Joker.cpp:38:47: warning: variable 'm2' set but not used [-Wunused-but-set-variable]
   38 |     int mid = (st + dr)/2 , i , poz , x , y , m2;
      |                                               ^~
Joker.cpp: In function 'int main()':
Joker.cpp:112:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     fscanf (fin,"%d%d%d",&n,&m,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:114:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:169:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |         fscanf (fin,"%d%d",&l,&r);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 160 ms 10860 KB Output is correct
4 Execution timed out 2079 ms 24356 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 300 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Incorrect 1 ms 332 KB Output isn't correct
9 Halted 0 ms 0 KB -