Submission #1279762

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279762		rtri	Joker (BOI20_joker)	C++20	0 / 100	171 ms	8248 KiB

Joker

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
int l, r;

struct UF {
  vector<int> sz, p, lazy, value;
  UF(int n) : sz(n, 1), p(n, -1), lazy(n, 0), value(n, 0) {}
  bool get_color(int a) {
    value[a] = (value[a] + lazy[a]) % 2;
    if (0 <= p[a])
      lazy[p[a]] = (lazy[p[a]] + lazy[a]) % 2;
    lazy[a] = 0;
    return value[a];
  }
  int find(int a) {
    get_color(a);
    return p[a] < 0 ? a : p[a] = find(p[a]);
  }
  void join(int a, int b) {
    int u = find(a), v = find(b);
    if (u == v)
      return;
    if (sz[u] < sz[v])
      swap(u, v);
    p[v] = u;
    sz[u] += sz[v];
    if (value[v] == value[u])
      lazy[v] = 1;
  }
};

int main() {
  cin >> n >> m >> q;

  vector<pair<int, int>> edg;
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    edg.push_back({a, b});
  }

  vector<tuple<int, int, int>> queries;
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    l--;
    r--;
    queries.push_back({l, r, i});
  }
  sort(queries.rbegin(), queries.rend());

  UF uf(n);

  vector<bool> ans(q);
  int prev_r = m;
  bool works = false;
  for (auto [l, r, idx] : queries) {
    for (int i = r; i < prev_r; i++) {
      auto [a, b] = edg[i];
      if (uf.find(a) == uf.find(b) && uf.get_color(a) == uf.get_color(b))
        works = true;
      uf.join(a, b);
    }
    ans[idx] = works;
    prev_r = r;
  }

  for (int i = 0; i < q; i++)
    if (ans[i])
      cout << "YES\n";
    else
      cout << "NO\n";

  return 0;
}

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