Submission #1050395

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050395		duckindog	Joker (BOI20_joker)	C++17	14 / 100	195 ms	860 KiB

Joker

#include <bits/stdc++.h>

using namespace std;

const int N = 2000 + 10;
int n, m, q;
vector<pair<int, int>> ad[N];
int co[N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

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

  auto color = [&](int st, int l, int r) { 
    bool ret = false;
    co[st] = 1;
    queue<int> q({st});
    while (q.size()) { 
      auto u = q.front(); q.pop();
      for (const auto& [v, id] : ad[u]) { 
        if (l <= id && id <= r) continue;
        if (co[v] == co[u]) ret = true;
        if (co[v]) continue;
        co[v] = co[u] ^ 3;
        q.push(v);
      }
    }
    return ret;
  };

  while (q--) { 
    int l, r; cin >> l >> r;
    memset(co, 0, sizeof co);
    bool answer = false;
    for (int i = 1; i <= n; ++i) if (!co[i]) answer |= color(i, l, r);
    cout << (answer ? "YES" : "NO") << "\n";
  }
}

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