Submission #1083607

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083607		VinhLuu	Joker (BOI20_joker)	C++17	100 / 100	240 ms	25148 KiB

Joker

#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define fi first
#define se second
//#define pb push_back
#define all(vin) vin.begin(), vin.end()

using namespace std;

typedef pair<int,int> pii;
typedef tuple<int,int,int> tp;
const int N = 2e5 + 5;
const int oo = 1e16;

int n, a[N], b[N], m, q;
vector<int> le[N], ri[N];

int pa[N], sz[N], val[N], cnt[N], e, ptl, ptr, w[N];
stack<tuple<int,int,int,int,int>> st;

int fin(int u){
  return pa[u] == u ? u : fin(pa[u]);
}

int cal(int u){
  return (pa[u] == u ? val[u] : val[u] ^ cal(pa[u]));
}

bool dsu(int u,int v){
  int x = fin(u);
  int y = fin(v);
//  cerr << u << " " << v << " " << x << " " << y << " " << cal(u) << " " << cal(v) << " g\n";
  if(x == y){
    if(cal(u) == cal(v)){
      st.push({0, 0, 0, 0, 0});
//      cerr << "                                     push" << 0 << "\n";
      e++;
      return 1;
    }
    return 0;
  }
  if(sz[x] < sz[y]) swap(x, y), swap(u, v);
  st.push({x, sz[x], y, pa[y], val[y]});
//  cerr << "                                     push" << x << " " << sz[x] << " " << y << " " << pa[y] << " " << (val[u] == val[v] ? 1 : 0) << "\n";
  sz[x] += sz[y];
  pa[y] = x;
  if(cal(u) == cal(v)) val[y] ^= 1;

  return 1;
}

void roll_back(){
  int x, sx, y, py, vly; tie(x, sx, y, py, vly) = st.top(); st.pop();
//  cerr << "                                     pop\n";
  if(!x){
    e--;
    return;
  }
  sz[x] = sx, pa[y] = py;
  val[y] = vly;
}

int f[N];

void solve(int l,int r,int pl,int pr){
  int mid = (l + r) / 2;
//  cerr << "                                              " << mid << " " << pl << " " << pr << " " << ptl << " " << ptr << " y\n";

  while(ptr > mid + 1){
    ptr--;
    cnt[ptr] += dsu(a[ptr], b[ptr]);
  }

  int mrk = ptl;
  if(e) f[mid] = -1;
  else f[mid] = 0;

  if(!e){
    for(int i = pl; i <= min(mid - 1, pr); i ++){
      while(ptl < i){
        ptl++;
        cnt[ptl] += dsu(a[ptl], b[ptl]);
      }
      if(e){
        f[mid] = i;
        break;
      }
    }
  }
  int nxt = mid - 1;
  if(f[mid] == -1) nxt = 1;
  else if(f[mid] == 0) nxt = max(1, mid - 1);
  else nxt = f[mid];

//  cerr << mid << " " << f[mid] << " " << nxt << " yyy\n";

  while(ptl >= pl){
    if(cnt[ptl]) cnt[ptl]--, roll_back();
    ptl--;
  }
  while(ptr > mid){
    ptr--;
    cnt[ptr] += dsu(a[ptr], b[ptr]);
  }
  if(l <= mid - 1) solve(l, mid - 1, pl, nxt);

  while(ptl >= pl){
    if(cnt[ptl]) cnt[ptl]--, roll_back();
    ptl--;
  }

  while(ptr <= r){
    if(cnt[ptr]) cnt[ptr]--, roll_back();
    ptr++;
  }
  while(ptl < nxt - 1){
    ptl++;
    cnt[ptl] += dsu(a[ptl], b[ptl]);
  }
  if(mid + 1 <= r) solve(mid + 1, r, nxt, pr);

  while(ptl >= pl){
    if(cnt[ptl]) cnt[ptl]--, roll_back();
    ptl--;
  }
  while(ptr <= r){
    if(cnt[ptr]) cnt[ptr]--, roll_back();
    ptr++;
  }
}

signed main(){
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  #define task "v"
  if(fopen(task ".inp","r")){
    freopen(task ".inp","r",stdin);
    freopen(task ".out","w",stdout);
  }
  cin >> n >> m >> q;
  for(int i = 1; i <= n; i ++) pa[i] = i, sz[i] = 1;
  for(int i = 1; i <= m; i ++){
    cin >> a[i] >> b[i];
  }
  ptl = 0, ptr = m + 1;
  solve(1, m, 1, m);

  while(q--){
    int l, r; cin >> l >> r;
    if(f[r] == 0){
      cout << "NO\n";
      continue;
    }
    if(f[r] < l) cout << "YES\n";
    else cout << "NO\n";
  }
}

Compilation message (stderr)

Joker.cpp:14:16: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+16' to '2147483647' [-Woverflow]
   14 | const int oo = 1e16;
      |                ^~~~
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:75:7: warning: unused variable 'mrk' [-Wunused-variable]
   75 |   int mrk = ptl;
      |       ^~~
Joker.cpp: In function 'int main()':
Joker.cpp:137:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     freopen(task ".inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:138:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |     freopen(task ".out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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