제출 #1172525

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172525		dombly	Joker (BOI20_joker)	C++20	14 / 100	2096 ms	14472 KiB

Joker

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

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