Submission #1279764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1279764		rtri	Joker (BOI20_joker)	C++20	0 / 100	2094 ms	13196 KiB

Joker

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

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