This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#ifdef LOCAL
#include <bits/debug.hpp>
#endif // LOCAL
#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Joker"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 2e5 + 7
using namespace std;
const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GetRandom(ll l, ll r) {
return uniform_int_distribution<ll> (l, r)(rng);
}
int n, m, q;
int f[maxn];
pair<int, int> qr[maxn];
struct dl { int u, v; } a[maxn];
struct DSU {
int lab[maxn], col[maxn], bad;
vector<pair<int, int>> E;
int *addr[6 * maxn], val[6 * maxn], top;
DSU() { memset(lab, -1, sizeof lab); }
void Add(int *a, int b) { if(*a != b) addr[++top] = a, val[top] = *a, *a = b; }
void RollBack(int Time) { while(top > Time) *addr[top] = val[top], --top; }
int get_rt(int u) {
return lab[u] < 0 ? u : get_rt(lab[u]);
}
int cl(int u) {
return lab[u] < 0 ? col[u] : (col[u] ^ cl(lab[u]));
}
void uni(int u, int v) {
int p = get_rt(u), q = get_rt(v);
if(p == q) {
Add(&bad, bad | (cl(u) == cl(v)));
return;
}
if(lab[p] > lab[q]) swap(p, q);
Add(&col[q], col[q] ^ (cl(u) == cl(v)));
Add(&lab[p], lab[p] + lab[q]), Add(&lab[q], p);
}
} Dsu;
/// 1 -> optL and r + 1 -> n already in DSU
void DnC(int l, int r, int optL, int optR) {
if(l > r) return;
int mid = (l + r) >> 1, pos = mid;
int Time = Dsu.top;
fid(i, r, mid + 1) Dsu.uni(a[i].u, a[i].v);
fi(i, optL, min(mid, optR)) {
if(i) Dsu.uni(a[i].u, a[i].v);
if(Dsu.bad) { pos = i; break; }
}
f[mid] = pos;
Dsu.RollBack(Time);
fid(i, r, mid) Dsu.uni(a[i].u, a[i].v);
DnC(l, mid - 1, optL, pos);
Dsu.RollBack(Time);
fi(i, optL, pos - 1) if(i) Dsu.uni(a[i].u, a[i].v);
DnC(mid + 1, r, pos, optR);
Dsu.RollBack(Time);
}
void solve()
{
cin >> n >> m >> q;
fi(i, 1, m) cin >> a[i].u >> a[i].v;
DnC(1, m, 0, m);
fi(i, 1, q) {
int l, r; cin >> l >> r;
cout << (l > f[r] ? "YES\n" : "NO\n");
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(Neco".inp", "r")) {
freopen(Neco".inp", "r", stdin);
freopen(Neco".out", "w", stdout);
}
int nTest = 1;
// cin >> nTest;
while(nTest--)
{
solve();
}
return 0;
}
Compilation message (stderr)
Joker.cpp: In function 'int main()':
Joker.cpp:117:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
117 | freopen(Neco".inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | freopen(Neco".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |