Submission #1279764

#TimeUsernameProblemLanguageResultExecution timeMemory
1279764rtriJoker (BOI20_joker)C++20
0 / 100
2094 ms13196 KiB
#include <bits/stdc++.h>
using namespace std;

int n, m, q;
int l, r;
vector<vector<pair<int, int>>> adj;

vector<int> vis;
bool cyc_find(int u, int color = 1, int p = -1) {
  vis[u] = color;
  for (auto [v, idx] : adj[u]) {
    if (l <= idx && idx <= r)
      continue;
    if (v != p) {
      if (vis[v] == vis[u])
        return true;
      if (!vis[v])
        cyc_find(v, color * -1, u);
    }
  }
  return false;
}

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

  adj.resize(n);
  for (int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    adj[a].push_back({b, i});
    adj[b].push_back({a, i});
  }

  vis.resize(n);
  for (int i = 0; i < q; i++) {
    cin >> l >> r;
    l--;
    r--;
    fill(vis.begin(), vis.end(), 0);
    bool ans = cyc_find(0);
    if (ans)
      cout << "YES\n";
    else
      cout << "NO\n";
  }

  return 0;
}
#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...