//Bismillahir-Rahmanir-Rahim
#include <bits/stdc++.h>
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,sse4,sse4.1,sse4.2,popcnt,avx,avx2")
#define pb push_back
#define pii pair <int, int>
#define pll pair <long long, long long>
#define pld pair <long double, long double>
#define ll long long
#define ld long double
#define x first
#define y second
#define all(v) v.begin(),v.end()
#define sz(s) (int)s.size()
#define skip continue
#define bpop(x) (ll)__builtin_popcountll(x)
using namespace std;
const int N = 2e5 + 7;
const int M = 1e3 + 7;
const int maxA = 2e6 + 7;
const int inf = 1e9 + 7;
const ll INF = 2e18 + 7;
const int MOD = 1e9 + 7;
const ld eps = 1e-9;
pii dir[] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
pii E[N];
vector <int> g[N];
int n, m, q, dist[N];
vector <pii> qs;
bool bfs(int st) {
queue <int> q;
q.push(st), dist[st] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto to : g[v]) {
if (dist[to] == -1)dist[to] = 1 - dist[v], q.push(to);
else if (dist[v] == dist[to]) {
//cout << v << ':' << dist[v] << ' ' << to << ':' << dist[to] << '\n';
return 1;
}
}
}
return 0;
}
void subtask12() {
for (auto p : qs) {
int l, r;
tie(l, r) = p;
for (int i = 1;i <= n;i++)g[i].clear(), dist[i] = -1;
for (int i = 1;i <= m;i++) {
if (l <= i && i <= r)skip;
g[E[i].x].pb(E[i].y), g[E[i].y].pb(E[i].x);
//cout << E[i].x << ' ' << E[i].y << '\n';
}
bool ans = 0;
for (int i = 1;i <= n;i++) {
if (dist[i] == -1)ans |= bfs(i);
}
cout << (ans ? "YES" : "NO") << '\n';
}
exit(0);
}
int color[N];
vector <int> vs[N];
int get(int x) {
return (x == color[x] ? x : color[x] = get(color[x]));
}
void subtask3() {
for (int i = 1;i <= n;i++)dist[i] = -1, color[i] = i, vs[i] = {i};
int pos = inf;
for (int i = 1;i <= m;i++) {
int x = E[i].x, y = E[i].y;
int Lx = get(x), Ly = get(y);
if (sz(vs[Lx]) > sz(vs[Ly]))swap(x, y), swap(Lx, Ly);
if (dist[x] == -1 && dist[y] == -1)dist[x] = 0, dist[y] = 1, color[x] = y, vs[y].pb(x), vs[x].clear();
else if (dist[x] == -1)dist[x] = 1 - dist[Ly], color[x] = Ly, vs[Ly].pb(x), vs[x].clear();
else {
if (Lx != Ly) {
color[Lx] = Ly;
for (auto v : vs[Lx])vs[Ly].pb(v), color[v] = Ly, dist[v] ^= (dist[v] == dist[to]);
vs[Lx].clear();
}
else if (dist[x] == dist[y]) {
pos = i;
break;
}
}
}
for (auto p : qs) {
int r = p.y;
if (r >= pos)cout << "YES\n";
else cout << "NO\n";
}
exit(0);
}
void solve() {
cin >> n >> m >> q;
for (int i = 1;i <= m;i++) {
int x, y;
cin >> x >> y;
E[i] = {x, y};
}
bool solve_for_pref = 1;
for (int i = 0;i < q;i++) {
int l, r;
cin >> l >> r;
qs.pb({l, r});
solve_for_pref &= (l == 1);
}
if (n <= 2000 && m <= 2000 && q <= 2000)subtask12();
if (solve_for_pref)subtask3();
}
signed main() {
//srand(time(NULL));
ios_base::sync_with_stdio(0);
cout.tie(0);
//freopen("tests.in", "r", stdin);
//freopen("milkorder.out", "w", stdout);
int test = 1;
//cin >> test;
for (int t = 1;t <= test;t++) {
//cout << "Case " << t << ": ";
solve();
}
return 0;
}
Compilation message
Joker.cpp: In function 'void subtask3()':
Joker.cpp:92:95: error: 'to' was not declared in this scope; did you mean 'tm'?
92 | for (auto v : vs[Lx])vs[Ly].pb(v), color[v] = Ly, dist[v] ^= (dist[v] == dist[to]);
| ^~
| tm
