Submission #262789

#	Time	Username	Problem	Language	Result	Execution time	Memory
262789		quocnguyen1012	Joker (BOI20_joker)	C++14	100 / 100	198 ms	13540 KiB

Joker

#include <bits/stdc++.h>
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ar array
 
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
 
const int maxn = 2e5 + 5;
 
struct pdsu
{
  vector<int> lab, off;
  vector<ar<int, 4>> saved;
  void init(int n)
  {
    saved.clear();
    lab.assign(n + 5, -1);
    off.assign(n + 5, 0);
  }
  ii finds(int u)
  {
    int now = 0;
    while(lab[u] >= 0){
      now ^= off[u];
      u = lab[u];
    }
    return mp(u, now);
  }
  bool merges(int __u, int __v)
  {
    ii x = finds(__u), y = finds(__v);
    if(x.fi == y.fi){
      if(x.se == y.se){
        return false;
      }
      ///saved.pb({-1, -1, -1, -1});
      return true;
    }
    if(lab[x.fi] > lab[y.fi]) swap(x, y);
    saved.pb({x.fi, y.fi, lab[x.fi], lab[y.fi]});
    lab[x.fi] += lab[y.fi]; lab[y.fi] = x.fi;
    off[y.fi] = x.se ^ y.se ^ 1;
    return true;
  }
  void rollback(void)
  {
    auto a = saved.back(); saved.pop_back();
    lab[a[0]] = a[2], lab[a[1]] = a[3];
  }
  void dbg(void)
  {
    for(int i = 1; i <= (int)lab.size() - 5; ++i){
      cerr << finds(i).fi << ' ';
    }
  }
}dsu;
 
void restore(int sz)
{
  while(dsu.saved.size() > sz){
    dsu.rollback();
  }
}
 
int U[maxn], V[maxn], op[maxn];
int N, M, Q;
 
void dnc(int l, int r, int opl, int opr)
{
  if(l > r) return;
  auto add = [&](int i)
  {
    if(i == M + 1) return true;
    return dsu.merges(U[i], V[i]);
  };
  //cerr << l << ' ' << r << ' ' << opl << ' ' << opr << '\n';
 
  int mid = (l + r) / 2;
  int sz = dsu.saved.size();
  int res = -1;
  /// calculate mid
  for(int i = l; i < mid; ++i){
    if(!add(i)){
      res = opr; assert(res == M + 1);
      break;
    }
  }
 
  int sz2 = dsu.saved.size();
  if(res == -1){
    int i = opr; while(i > opl && add(i)) --i;
    res = i;
  }
  op[mid] = res;
 
 
  if(op[mid] != M + 1){
    restore(sz2);
    if(add(mid))
      dnc(mid + 1, r, op[mid], opr);
    else{
      for(int i = mid + 1; i <= r; ++i)
        op[i] = M + 1;
    }
  }
  else{
    for(int i = mid + 1; i <= r ; ++i)
      op[i] = M + 1;
  }
  restore(sz);
  for(int i = op[mid] + 1; i <= opr; ++i)
    assert(add(i));
  dnc(l, mid - 1, opl, op[mid]);
  restore(sz);
}
 
signed main(void){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #ifdef LOCAL
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  #endif // LOCAL
  cin >> N >> M >> Q; dsu.init(N);
  for(int i = 1; i <= M; ++i){
    cin >> U[i] >> V[i];
    //op[i] = M + 1;
  }
  dnc(1, M, 1, M + 1);
  #ifdef LOCAL
  //for(int i = 1; i <= M; ++i) cerr << op[i] << ' ' ; cerr << '\n';
  for(int i = 1; i <= M; ++i){
    restore(0);
    bool ok = false;
    for(int j = 1; j <= i; ++j){
      if(!dsu.merges(U[j], V[j])){
        ok = true;
      }
    }
    if(ok){
     // cerr << M + 1 << ' ';
      if(op[i] != M + 1){
        cout << -1;
        return 0;
      }
      continue;
    }
    int res = M;
    while(res > 1){
      if(dsu.merges(U[res], V[res])){
        --res;
      }
      else break;
    }
    //cerr << res << ' ';
    if(op[i] != res){
      cout << -1;
      return 0;
    }
  }
  cout << 0;
  return 0;
  #endif // LOCAL
  while(Q--){
    int l, r; cin >> l >> r;
    if(r >= op[l]) cout << "NO\n";
    else cout << "YES\n";
  }
}

Compilation message (stderr)

Joker.cpp: In function 'void restore(int)':
Joker.cpp:66:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 4> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   while(dsu.saved.size() > sz){
      |         ~~~~~~~~~~~~~~~~~^~~~

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