#pragma GCC optimize("O2")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define pb push_back
#define f first
#define s second
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> piii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<piii> viii;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1000100, MAXK = 23;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const ll INF = 1e16;
const ld PI = asin(1) * 2;
void setIO () {
FAST_IO;
}
void setIO (string s) {
setIO();
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
int n, m, q;
int cycleFound = 0;
int par[MAXN], sz[MAXN];
int unitCnt = 0;
//stack<pair<int, pii>> st; /// {v, par[v], sz[v]}
stack<int> st;
int find (int a) {
if (par[a] == a) return a;
//par[a] = find(par[a]);
return find(par[a]);
}
bool same (int a, int b){
return find(a) == find(b);
}
bool inCycle (int a) {
int nA = (a > n ? (a-n) : (a+n));
return same(a, nA);
}
void unite (int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
// bool wassame = same(a, nA);
if (sz[a] < sz[b]) swap(a,b);
//sizes.push(st.size());
//st.push({b, {par[b], sz[b]});
st.push(b);
unitCnt++;
par[b] = a;
sz[a] += sz[b];
if (inCycle(b)) {
cycleFound++;
// cout << " cyclefoind = " << a << " " << nA << endl;
}
}
void rollback() {
/*auto pp = st.top();
st.pop();
int b = st.f;
int prevPar = st.s.f;
int prevSz = st.s.s;
sz[b] = prevSz;
sz[par[b]] -= sz[b];
par[b] = prevPar;*/
int b = st.top();
if (inCycle(b)) cycleFound--;
st.pop();
sz[par[b]] -= sz[b];
par[b] = b;
unitCnt--;
}
void resetDSU () {
while (!st.empty()) {st.pop();}
FOR(i ,1 ,2*n) par[i] = i;
FOR(i ,1, 2*n) sz[i] = 1;
cycleFound = false;
unitCnt= 0;
}
//vi adj[MAXN];
pii edges[MAXN];
void addE (int id) {
if (id > m) return;
if (id < 1) return;
int u = edges[id].f;
int v = edges[id].s;
unite (u, v+n);
unite (v, u+n);
// cout <<" added " << u << "-" << (v+n) << " and " << v << "-" << (u+n) << endl;
}
int last[MAXN];
void rec (int l1, int l2, int r1, int r2) {
int tmp = unitCnt;
int lmid = (l1+l2)/2;
FOR(i, l1, lmid-1) addE(i);
int rmid;
for (int i = r2; i >= r1; i--){
addE(i);
if (cycleFound) {
last[lmid] = i;
rmid = i;
break;
}
}
// cout << " rec [" << l1 << "," << l2 << "] [" << r1 << "," << r2 << "]" << endl;
// cout << " lmid = " << lmid << " rmid = " << rmid << endl;
while (unitCnt > tmp) {
rollback();
}
if (l1 <= lmid-1) {
FOR(i, rmid+1, r2) addE(i);
rec(l1, lmid-1, r1, rmid);
}
while (unitCnt > tmp) {
rollback();
}
if(lmid+1 <= l2) {
FOR(i, l1, lmid) addE(i);
rec(lmid+1, l2, max(lmid+1, r1), r2);
}
while (unitCnt > tmp) {
rollback();
}
}
int main() {
setIO();
cin >> n >> m >> q;
FOR(i, 1, m) {
int u, v; cin >> u >> v;
edges[i] = {u,v};
}
resetDSU();
rec(1, m, 1, m+1);
// FOR(i ,1, m) cout << " i = " << i << " last = "<< last[i] << endl;
REP(q) {
int le, ri; cin >> le >> ri;
if (ri < last[le]) cout << "YES\n";
else cout << "NO\n";
}
return 0;
}
Compilation message (stderr)
Joker.cpp: In function 'void setIO(std::string)':
Joker.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
36 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | freopen((s+".out").c_str(),"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... |