Submission #1049364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049364		duckindog	Joker (BOI20_joker)	C++17	0 / 100	191 ms	8824 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m, q;
pair<int, int> edge[N];

vector<tuple<int, int, int, int>> undo;
int id[N], cnt;
int root(int u) { return id[u] < 0 ? u : root(id[u]); }
inline void add(int u, int v) { 
  u = root(u); v = root(v);
  if (u == v) {
    cnt += 1;
    undo.emplace_back(0, -1, 0, -1);
    return;
  }
  if (id[u] > id[v]) swap(u, v);
  undo.emplace_back(u, id[u], v, id[v]);
  id[u] += id[v];
  id[v] = u;
}
inline void rollBack() { 
  auto [u, idu, v, idv] = undo.back(); undo.pop_back();
  cnt -= !u;
  id[u] = idu;
  id[v] = idv;
}

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) add(edge[i].first, edge[i].second);
  for (int i = rt; i >= max(mid + 1, lt); --i) add(edge[i].first, edge[i].second);

  for (int i = max(mid + 1, lt); i <= rt; ++i) {
    const auto& [u, v] = edge[i];
    if (cnt) ret = i - 1;
    rollBack();
  } if (cnt) ret = rt;

  add(edge[mid].first, edge[mid].second);
  dnc(mid + 1, r, !ret ? lt : ret, rt);
  for (int i = l; i <= mid; ++i) rollBack();

  for (int i = rt; i > (!ret ? rt : ret); --i) add(edge[i].first, edge[i].second);
  dnc(l, mid - 1, lt, (!ret ? rt : ret));
  for (int i = rt; i > (!ret ? rt : ret); --i) 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].first >> edge[i].second;

  memset(id, -1, sizeof id);
  dnc(1, m, 1, m);

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

Compilation message (stderr)

Joker.cpp: In function 'void dnc(int, int, int, int)':
Joker.cpp:34:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |   int mid = l + r >> 1;
      |             ~~^~~
Joker.cpp:41:17: warning: unused structured binding declaration [-Wunused-variable]
   41 |     const auto& [u, v] = edge[i];
      |                 ^~~~~~

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