제출 #1172525

#제출 시각아이디문제언어결과실행 시간메모리
1172525domblyJoker (BOI20_joker)C++20
14 / 100
2096 ms14472 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];
vector<int> g[N];

void Add(int u, int v) {
  g[u].push_back(v);
  g[v].push_back(u);
}

bool check;

void Dfs(int u) {
  for(int j : g[u]) {
    if(col[j] == -1) {
      col[j] = col[u] ^ 1;
      Dfs(j);
    } else {
      if(col[u] == col[j]) check = false;
    }
  }
}

bool Solve(int l, int r) {
  for(int i = 1; i <= n; i++) {
    col[i] = -1;
    g[i].clear();
  }
  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(col[i] == -1) {
      col[i] = 0;
      check = true;
      Dfs(i);
      ok &= check;
    }
  }
  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...