Submission #1093510

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093510		zNatsumi	Joker (BOI20_joker)	C++17	14 / 100	2047 ms	15808 KiB

Joker

#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;
}

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