Submission #1050559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050559		duckindog	Joker (BOI20_joker)	C++17	14 / 100	40 ms	9820 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;
  bool mk[N];

  void clear() { 
    memset(id, -1, (n + 1) * sizeof(int));
    memset(co, 0, (n + 1) * sizeof(int));
    memset(mk, false, (n + 1) * sizeof(int));
    cnt = 0;
  }

  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); }
  void add(int u, int v) { 
    int oU = u, oV = v;

    u = root(u); v = root(v);
    if (u == v) { cnt += color(oU) == color(oV); return; }
    
    if (id[u] > id[v]) swap(u, v);
    if (color(oU) == color(oV)) mk[v] ^= 1;

    id[u] += id[v];
    id[v] = u; 
  }
} T;

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m >> q;
  for (int i = 1; i <= m; ++i) cin >> edge[i];
  
  while (q--) { 
    int l, r; cin >> l >> r;
    
    T.clear();
    for (int i = 1; i < l; ++i) T.add(edge[i].u, edge[i].v);
    for (int i = m; i > r; --i) T.add(edge[i].u, edge[i].v);

    cout << (T.cnt ? "YES" : "NO") << "\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) {
      |                                             ^~~~

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