Submission #1130475

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130475		joelgun14	Joker (BOI20_joker)	C++20	25 / 100	105 ms	11444 KiB

Joker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define endl "\n"
#define ll long long
#define mp make_pair
#define ins insert
#define lb lower_bound
#define pb push_back
#define ub upper_bound
#define lll __int128
#define fi first
#define se second
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int lim = 2e5 + 5;
struct disjoint_set {
  int h[lim], sz[lim];
  bool par[lim], cycle[lim];
  int cnt = 0;
  // x, y
  vector<pair<int, int>> rb;
  disjoint_set() {
    memset(h, -1, sizeof(h));
    fill(sz, sz + lim, 1);
    memset(par, 0, sizeof(par));
    memset(cycle, 0, sizeof(cycle));
  }
  int fh(int nd) {
    return h[nd] == -1 ? nd : fh(h[nd]);
  }
  bool get_par(int nd) {
    return h[nd] == -1 ? par[nd] : par[nd] ^ get_par(h[nd]);
  }
  void merge(int x, int y) {
    int xh = fh(x), yh = fh(y);
    if(xh != yh) {
      if(sz[xh] < sz[yh])
        swap(xh, yh);
      if(get_par(x) == get_par(y))
        par[yh] = 1;
      h[yh] = xh;
      sz[xh] += sz[yh];
      rb.pb(mp(xh, yh));
    }
    else {
      if(get_par(x) == get_par(y)) {
        cycle[xh] = 1;
        rb.pb(mp(xh, xh));
        ++cnt;
      }
      else {
        rb.pb(mp(-1, -1));
      }
    }
  }
  void rollback() {
    if(rb.size()) {
      if(rb.back() != mp(-1, -1)) {
        pair<int, int> cur = rb.back();
        if(cur.fi == cur.se) {
          --cnt;
          cycle[cur.fi] = 0;
        }
        else {
          h[cur.se] = -1;
          sz[cur.fi] -= sz[cur.se];
          par[cur.se] = 0;
        }
      }
      rb.pop_back();
    }
  }
  void clear() {
    while(rb.size())
      rollback();
  }
} dsu;
int main() {
  ios_base::sync_with_stdio(0); cin.tie(NULL);
  int n, m, q;
  cin >> n >> m >> q;
  // do mo's algo
  pair<int, int> adj[m + 1];
  for(int i = 1; i <= m; ++i) {
    cin >> adj[i].fi >> adj[i].se;
  }
  int blk = sqrt(m);
  vector<pair<pair<int, int>, int>> a[m / blk + 5];
  for(int i = 0; i < q; ++i) {
    int x, y;
    cin >> x >> y;
    a[x / blk].pb(mp(mp(y, x), i));
  }
  int r = -blk;
  int ans[q];
  memset(ans, -1, sizeof(ans));
  for(auto &p : a) {
    // cerr << r << endl;
    dsu.clear();
    sort(p.begin(), p.end());
    reverse(p.begin(), p.end());
    // largest to smallest r
    for(auto &x : p)
      swap(x.fi.fi, x.fi.se);
    // merge lefts
    for(int i = max(r, 1); i < min(m + 1, r + blk); ++i) {
      dsu.merge(adj[i].fi, adj[i].se);
      // cerr << "USE1 " << i << endl;
    }
    r += blk;
    int cr = m + 1;
    for(auto x : p) {
      // do queries
      // merge rights
      while(cr - 1 > x.fi.se) {
        --cr;
        // cerr << "USE2 " << cr << endl;
        dsu.merge(adj[cr].fi, adj[cr].se);
      }
      for(int i = max(r, 1); i < x.fi.fi; ++i) {
        // cerr << "USE3 " << i << endl;
        dsu.merge(adj[i].fi, adj[i].se);
      }
      // cerr << x.fi.fi << " " << x.fi.se << " " << cr << endl;
      ans[x.se] = dsu.cnt > 0;
      for(int i = max(r, 1); i < x.fi.fi; ++i) {
        // cerr << "REMOVE " << i << endl;
        dsu.rollback();
      }
    }
    // cerr << "SEP" << endl;
  }
  for(auto x : ans) {
    if(x == 1)
      cout << "YES" << endl;
    else if(x == 0)
      cout << "NO" << endl;
    else 
      cout << "ERROR" << endl;
  }
  return 0;
}

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