제출 #1093510

#제출 시각아이디문제언어결과실행 시간메모리
1093510zNatsumiJoker (BOI20_joker)C++17
14 / 100
2047 ms15808 KiB
#include <bits/stdc++.h>

using namespace std;

#define ii pair<int, int>
#define fi first
#define se second
#define all(x) x.begin(), x.end()

const int N = 2e5 + 5;

int n, m, q;
vector<ii> ad[N], que;

namespace sub1{
  int val[N];

  void solve(){
    for(auto x : que){
      int l, r; tie(l, r) = x;

      for(int i = 1; i <= n; i++) val[i] = -1;

      bool ok = false;
      for(int i = 1; i <= n; i++) if(val[i] == -1){
        queue<int> q;
        q.push(i);
        val[i] = 0;

        while(q.size()){
          auto u = q.front(); q.pop();

          for(auto [v, idx] : ad[u]){
            if(l <= idx && idx <= r) continue;
            if(val[v] == -1){
              q.push(v);
              val[v] = val[u] ^ 1;
            }
            else if(val[v] == val[u]){
              ok = true;
              break;
            }
          }
        }
        if(ok) break;
      }
      cout << (ok ? "YES\n" : "NO\n");
    }
  }
}

int32_t main(){
  cin.tie(0)->sync_with_stdio(0);
//  #define task "test"
//  if(fopen(task ".inp", "r")){
//    freopen(task ".inp", "r", stdin);
//    freopen(task ".out", "w", stdout);
//  }
  cin >> n >> m >> q;
  for(int i = 1; i <= m; i++){
    int u, v; cin >> u >> v;
    ad[u].push_back({v, i});
    ad[v].push_back({u, i});
  }
  for(int i = 1; i <= q; i++){
    int l, r; cin >> l >> r;
    que.push_back({l, r});
  }

  sub1::solve();


  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...