Submission #415012

#	Time	Username	Problem	Language	Result	Execution time	Memory
415012		Ruxandra985	Joker (BOI20_joker)	C++14	100 / 100	496 ms	13360 KiB

Joker

#include <bits/stdc++.h>
#define DIMN 400010
using namespace std;
int tt[DIMN];
int sz[DIMN] , opt[DIMN];
int n , m , where;
pair <int , int> mch[DIMN];
vector <int> s;
vector <int> v;

int root (int x){
    while (tt[x] != x)
        x = tt[x];
    return x;
}

inline void unite (int x, int y){
    int radx = root(x), rady = root(y);
    if (radx == rady)
        return;
    if (sz[radx] < sz[rady])
        swap (radx,rady);

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

inline int unite_init (int x , int y){
    int radx = root(x) , radnx , rady = root(y) , radny;

    if (radx == rady)
        return 0;

    radnx = root(n + x);
    radny = root(n + y);

    unite(radx , radny);
    unite(rady , radnx);

    return 1;


}

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

    if (mid <= where){
        if (mid + 1 <= dr)
            solve(mid + 1 , dr , l , r);
        return;
    }

    init = s.size();

    for (i = min(dr , m) ; i >= mid ; i--){
        x = mch[i].first;
        y = mch[i].second;

        if (!unite_init(x , y))
            break;
    }

    if (i >= mid){ /// nu se poate cu toate
        where = i;



        while (s.size() != init){

            y = s.back();
            s.pop_back();
            sz[tt[y]] -= sz[y];
            tt[y] = y;

        }

        /// te duci doar in dreapta
        if (mid + 1 <= dr)
            solve(mid + 1 , dr , l , r);



        return;

    }



    init2 = s.size();

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

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

        if (!unite_init(x , y))
            break;
        poz = i;

    }
    opt[mid] = poz;

    while (s.size() != init2){

        y = s.back();
        s.pop_back();
        sz[tt[y]] -= sz[y];
        tt[y] = y;

    }

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

    while (s.size() != init){

        y = s.back();
        s.pop_back();
        sz[tt[y]] -= sz[y];
        tt[y] = y;

    }

    if (mid + 1 <= dr){

        for (i = l + 1 ; i <= poz ; i++){
            x = mch[i].first;
            y = mch[i].second;
            unite_init (x , y);
            //v.push_back(i);

        }

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

        while (s.size() != init){

            y = s.back();
            s.pop_back();
            sz[tt[y]] -= sz[y];
            tt[y] = y;

        }
    }
}

int main() {
    FILE *fin = stdin;
    FILE *fout = stdout;
    int q , i , 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);
    }

    for (i = 1; i <= 2 * n ; ++i){
        tt[i] = i;
        sz[i] = 1;
    }
    solve(1, m + 1 , 0 , m);
    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 (stderr)

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:70:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |         while (s.size() != init){
      |                ~~~~~~~~~^~~~~~~
Joker.cpp:106:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |     while (s.size() != init2){
      |            ~~~~~~~~~^~~~~~~~
Joker.cpp:118:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  118 |     while (s.size() != init){
      |            ~~~~~~~~~^~~~~~~
Joker.cpp:139:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  139 |         while (s.size() != init){
      |                ~~~~~~~~~^~~~~~~
Joker.cpp: In function 'int main()':
Joker.cpp:154:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |     fscanf (fin,"%d%d%d",&n,&m,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:157:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         fscanf (fin,"%d%d",&mch[i].first,&mch[i].second);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:166:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |         fscanf (fin,"%d%d",&l,&r);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 10 / 10
• Subtask 5: 22 / 22
• Subtask 6: 29 / 29