This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
const int N = 1e6 + 1, mod = 998244353;
const ll inf = 1e9;
double eps = 1e-15;
bool flg = 0;
bool ok = 1, was[N];
vector<pii> g(N);
int p[N], pr[N];
int sz[N], pt[N];
vector<pii> h;
pii get(int x) {
if (p[x] == x) return {x, 0};
pii val = get(p[x]);
return {val.f, ((pr[x] + val.s) & 1)};
}
inline void add(int id) {
int u = g[id].f;
int v = g[id].s;
if (u == -1) return;
pii x = get(u);
pii y = get(v);
if (x.f == y.f) {
if (x.s == y.s) {
if (ok) {
h.push_back({-1, -1});
ok = 0;
}
}
return;
}
if (sz[x.f] > sz[y.f]) swap(x, y);
h.push_back({x.f, sz[x.f]});
h.push_back({y.f, sz[y.f]});
p[x.f] = y.f;
pr[x.f] = ((x.s + y.s + 1) & 1);
sz[y.f] += sz[x.f];
}
inline void rb() {
while (sz(h) && !pt[sz(h)]) {
pii x = h.back();
h.pop_back();
if (x.f == -1) {
ok = 1;
continue;
}
p[x.f] = x.f;
pr[x.f] = 0;
sz[x.f] = x.s;
}
pt[sz(h)]--;
}
int ps[N];
void f(int l, int r, int tr) {
if (l > r) return;
int m = (l + r) / 2;
pt[sz(h)]++;
for (int i = m - 1; i >= l; i--)
add(i);
pt[sz(h)]++;
for (int i = tr; i >= m; i--) {
add(i);
if (!ok) {
ps[m] = i;
break;
}
}
rb();
add(m);
f(m + 1, r, tr);
rb();
if (!ps[m]) return;
pt[sz(h)]++;
for (int i = tr; i > ps[m]; i--)
add(i);
f(l, m - 1, ps[m]);
rb();
}
void slv() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[i] = {u, v};
}
g[m + 1] = {-1, -1};
for (int i = 1; i <= n; i++)
p[i] = i, sz[i] = 1;
f(1, m, m + 1);
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
l = max(l, 1);
r = min(r, m);
if (ps[l] > r) cout << "YES\n";
else cout << "NO\n";
}
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int tp = 1;
if (flg) cin >> tp;
while (tp--) {
slv();
}
}
Compilation message (stderr)
Joker.cpp:132:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
132 | main() {
| ^~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |