Submission #1172526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172526		dombly	Joker (BOI20_joker)	C++20	14 / 100	2092 ms	8488 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

const int inf = 1e9 + 7;

int col[N], n, m, q, u[N], v[N], par[N];
vector<int> g[N];

void Init(int n) {
  for(int i = 1; i <= n; i++) par[i] = i;
}

int get(int x) {
  return (x == par[x] ? x : par[x] = get(par[x]));
}

void unite(int u, int v) {
  u = get(u); v = get(v);
  if(u != v) par[u] = v;
}

void Add(int u, int v) {
  unite(u, n + v);
  unite(v, n + u);
}

bool Solve(int l, int r) {
  for(int i = 1; i <= n; i++) {
    col[i] = -1;
    g[i].clear();
  }
  Init(n * 2);
  for(int i = 1; i < l; i++) Add(u[i], v[i]);
  for(int i = r + 1; i <= m; i++) Add(u[i], v[i]);
  bool ok = true;
  for(int i = 1; i <= n; i++) {
    if(get(i) == get(i + n)) ok = false;
  }
  return ok;
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  cin >> n >> m >> q;
  for(int i = 1; i <= m; i++) cin >> u[i] >> v[i];
  while(q--) {
    int l, r;
    cin >> l >> r;
    cout << (Solve(l, r) ? "NO\n" : "YES\n");
  }
}

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