Submission #1050727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050727		duckindog	Joker (BOI20_joker)	C++17	100 / 100	226 ms	16052 KiB

Joker

#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 200'000 + 10;
int n, m, q;
struct Edge { 
  int u, v;
  friend istream& operator >> (istream& is, auto& rhs) { 
    return is >> rhs.u >> rhs.v;
  }
} edge[N];
 
struct DSU { 
  int id[N], co[N], cnt;
  vector<tuple<int, int, int, int, int, int>> undo;
  bool mk[N];
  
  int root(int u) { return id[u] < 0 ? u : root(id[u]); }
  bool chk(int u) { return id[u] < 0 ? mk[u] : mk[u] ^ chk(id[u]); }
  inline int color(int u) { return co[u] ^ chk(u); }
  inline void add(int u, int v) { 
    int oU = u, oV = v;
 
    u = root(u); v = root(v);
    if (u == v) { 
      undo.emplace_back(0, 0, 0, 0, 0, cnt);
      cnt += color(oU) == color(oV); 
      return; 
    }

    if (id[u] > id[v]) swap(u, v);

    undo.emplace_back(u, id[u], v, id[v], mk[v], cnt);

    if (color(oU) == color(oV)) mk[v] ^= 1;
    id[u] += id[v];
    id[v] = u; 
  }
  inline void rollBack() { 
    auto [u, idU, v, idV, mkV, pCnt] = undo.back(); undo.pop_back();
    id[u] = idU;
    id[v] = idV;
    mk[v] = mkV;
    cnt = pCnt;
  }
} T;

int f[N];
void dnc(int l, int r, int lt, int rt) { 
  if (l > r) return;
  int mid = l + r >> 1;
  auto& ret = f[mid];
  
  for (int i = l; i < mid; ++i) T.add(edge[i].u, edge[i].v);
  for (int i = rt; i >= max(mid + 1, lt); --i) T.add(edge[i].u, edge[i].v);
 
  for (int i = max(mid + 1, lt); i <= rt; ++i) {
    const auto& [u, v] = edge[i];
    if (T.cnt) ret = i - 1;
    T.rollBack();
  } if (T.cnt) ret = rt;
  
  int nxtr = (!ret ? max(mid, lt) : ret),
      nxtl = (!ret ? mid : ret);

  T.add(edge[mid].u, edge[mid].v);
  dnc(mid + 1, r, nxtr, rt);
  for (int i = l; i <= mid; ++i) T.rollBack();

  for (int i = rt; i > nxtl; --i) T.add(edge[i].u, edge[i].v);
  dnc(l, mid - 1, lt, nxtl);
  for (int i = rt; i > nxtl; --i) T.rollBack();
}

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) cin >> edge[i];

  memset(T.id, -1, sizeof T.id);
  T.cnt = 0;

  dnc(1, m, 1, m);
  while (q--) { 
    int l, r; cin >> l >> r;
    cout << (r <= f[l] ? "YES" : "NO") << "\n";
  }
  cerr << 1.0 * clock() / CLOCKS_PER_SEC << "\n";
}

Compilation message (stderr)

Joker.cpp:9:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
    9 |   friend istream& operator >> (istream& is, auto& rhs) {
      |                                             ^~~~
Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:52:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid = l + r >> 1;
      |             ~~^~~
Joker.cpp:59:17: warning: unused structured binding declaration [-Wunused-variable]
   59 |     const auto& [u, v] = edge[i];
      |                 ^~~~~~

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