Submission #1172526

#TimeUsernameProblemLanguageResultExecution timeMemory
1172526domblyJoker (BOI20_joker)C++20
14 / 100
2092 ms8488 KiB
#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");
  }
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...