Submission #1130277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130277		mircea_007	Joker (BOI20_joker)	C++20	0 / 100	88 ms	10152 KiB

Joker

#include <stdio.h>

#include <algorithm>
#include <vector>

struct Edge {
  int a, b;
  Edge( int a = 0, int b = 0 ): a(a), b(b) {}
};

namespace BipCheck {
  std::vector<int> dsu, siz;
  int bad_ops;

  struct Join {
    int a, b; // a != b daca se unesc componente, a == b daca e paritate gresita
    Join( int a, int b ): a(a), b(b) {}

    inline void apply() {
      if( a == b ){
        bad_ops++;
        return;
      }
      
      if( siz[a] > siz[b] ){
        dsu[b] = a;
        siz[a] += siz[b];
      }else{
        dsu[a] = b;
        siz[b] += siz[a];
      }
    }

    inline void undo() {
      if( a == b ){
        bad_ops--;
        return;
      }
      
      if( dsu[a] == a ){
        siz[a] -= siz[b];
        dsu[b] = b;
      }else{
        siz[b] -= siz[a];
        dsu[a] = a;
      }
    }
  };
  std::vector<Join> stack;

  inline bool check() { return !bad_ops; }
  inline int save() { return (int)stack.size(); }
  void rollback( int time ) {
    while( (int)stack.size() > time ){
      stack.back().undo();
      stack.pop_back();
    }
  }
  
  void init( int n ) {
    dsu.resize( n );
    for( int i = 0; i < n; i++ )
      dsu[i] = i;

    siz.assign( n, 1 );
    bad_ops = 0;
    stack.clear();
  }

  void push( Edge e ) {
    int pa = false, pb = false;

    while( dsu[e.a] != e.a ){
      e.a = dsu[e.a];
      pa = !pa;
    }
    
    while( dsu[e.b] != e.b ){
      e.b = dsu[e.b];
      pb = !pb;
    }

    if( e.a == e.b && (pa != pb) ) // nu facem nimic?
      return;

    Join J(e.a, e.b);
    stack.push_back( J );
    stack.back().apply();
  }
};

const int MAXM = 2e5;
Edge v[MAXM];

const int BSIZ = 2000; // sqrt(NlogN)
struct Query {
  int st, dr, idx, ans;
  Query( int st, int dr, int idx ): st(st), dr(dr), idx(idx), ans(-1) {}
};

int main() {
  int nodes, n, q;
  scanf( "%d%d%d", &nodes, &n, &q );

  for( int i = 0; i < n; i++ ){
    int a, b;
    scanf( "%d%d", &a, &b );
    v[i] = Edge(--a, --b);
  }

  std::vector<Query> qs;
  for( int i = 0; i < q; i++ ){
    int st, dr;
    scanf( "%d%d", &st, &dr );
    qs.emplace_back( --st, --dr, i );
  }

  std::sort( qs.begin(), qs.end(), []( const Query &a, const Query &b ) -> bool {
    if( a.st / BSIZ == b.st / BSIZ )
      return a.st < b.st;
    return a.dr > b.dr;
  } );

  BipCheck::init( nodes );

  int qidx = 0;
  for( int buk = 0; buk * BSIZ < n; buk++ ){
    int buk_begin = buk * BSIZ;
    int buk_end = std::min( (buk + 1) * BSIZ, n );
    
    int init = BipCheck::save();
    
    int dreapta = n - 1;
    while( qidx < (int)qs.size() && qs[qidx].st < buk_end ){
      while( dreapta > qs[qidx].dr )
        BipCheck::push( v[dreapta--] );

      int before_prefix = BipCheck::save();
      for( int i = buk_begin; i < qs[qidx].st; i++ )
        BipCheck::push( v[i] );
      
      qs[qidx].ans = BipCheck::check();
      BipCheck::rollback( before_prefix );

      qidx++;
    }

    BipCheck::rollback( init );
    for( int i = buk_begin; i < buk_end; i++ )
      BipCheck::push( v[i] );
  }

  std::sort( qs.begin(), qs.end(), []( const Query &a, const Query &b ) -> bool {
    return a.idx < b.idx;
  } );
  for( Query Q : qs )
    fputs( (Q.ans == false) ? "YES\n" : "NO\n", stdout ); // avem ciclu impar <=> este bipartit

  return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'int main()':
Joker.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |   scanf( "%d%d%d", &nodes, &n, &q );
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |     scanf( "%d%d", &a, &b );
      |     ~~~~~^~~~~~~~~~~~~~~~~~
Joker.cpp:114:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |     scanf( "%d%d", &st, &dr );
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~

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