#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int inf = int(1e18);
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> p2;
#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define sz(container) ((int)container.size())
#define all(x) begin(x),end(x)
#define ceildiv(x,y) ((x + y - 1) / (y))
inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
#define _LOCAL _DEBUG
#if _LOCAL
#define assert(x) if (!(x)) __debugbreak()
#endif
struct change
{
int a, b;
int oldpar, oldxor, oldsize;
};
struct UF
{
vector<change> updates;
vi size;
vi par;
vi parity;
UF(int n) : size(n, 1), parity(n), par(n)
{
rep(i, n)par[i] = i;
}
int find(int x) { return x == par[x] ? x : find(par[x]); }
int getparity(int x) { return x == par[x] ? parity[x] : parity[x] ^ getparity(par[x]); }
bool oddcycle(int a, int b)
{
return getparity(a) == getparity(b);
}
void merge(int a, int b)
{
if (size[find(a)] < size[find(b)]) swap(a, b);
int childa = a;
int childb = b;
a = find(a); b = find(b);
change c({ a,b,par[b],parity[b],size[a] });
updates.push_back(c);
if (a != b)
{
parity[b] = getparity(childb) ^ getparity(childa) ^ 1;
size[a] += size[b];
par[b] = a;
}
}
void rollback()
{
change c = updates.back();
updates.pop_back();
par[c.b] = c.oldpar;
parity[c.b] = c.oldxor;
size[c.a] = c.oldsize;
}
};
UF uf(0);
vector<p2> edgelist;
bool add(int i)
{
int a, b;
tie(a, b) = edgelist[i];
int ret = 0;
if (uf.find(a) == uf.find(b)) ret = uf.oddcycle(a, b);
uf.merge(a, b);
return ret;
};
vi rightp;
void dc(int l, int r, int hr, bool yes) // we have added edges [0,i) and (r, M)
{
if (l==r)
{
//cout << l << ": " << hr << "\n";
rightp[l] = (yes ? inf : hr);
return;
}
int mid = (l + r) / 2;
// left side
// update hr
repp(i, l, mid) add(i);
int cnt = 0;
int newhr = hr;
for (int i = hr; i >= mid; i--)
{
cnt++;
newhr = i;
if (add(i))
{
break;
}
}
rep(i, cnt) uf.rollback();
repp(i, l, mid) uf.rollback();
for (int i = hr, j = cnt-1; j > 0; i--, j--) add(i);
dc(l, mid, newhr, yes);
rep(i, cnt-1) uf.rollback();
// right side
bool newyes = 0;
int newhl = newhr;
repp(i, l, mid+1) newyes |= add(i);
dc(mid + 1, r, hr, newyes);
repp(i, l, mid+1) uf.rollback();
}
signed main()
{
fast();
//ifstream in("C:\\Users\\Matis\\Desktop\\comp_prog\\x64\\debug\\in.txt");
//cin.rdbuf(in.rdbuf());
int n, m, q;
cin >> n >> m >> q;
rep(i, m)
{
int a, b;
cin >> a >> b;
a--; b--;
edgelist.emplace_back(a, b);
}
//shuffle(edgelist.begin(), prev(edgelist.end()), mt19937(3436876));
/*uf = UF(n);
vi right(m, inf);
bool anyodd = 0;
rep(i, m)
{
int lo = i;
int hi = m;
while (lo + 1 < hi)
{
int mid = (lo + hi) / 2;
bool odd = 0;
for (int j = m - 1; j >= mid; j--) odd |= add(j);
for (int j = m - 1; j >= mid; j--) uf.rollback();
if (odd) lo = mid;
else hi = mid;
}
right[i] = lo;
if (anyodd) right[i] = inf;
anyodd |= add(i);
}*/
uf = UF(n);
rightp.resize(m);
dc(0, m-1, m-1, 0);
//assert(right == rightp);
//vvi queries(m);
while (q--)
{
int l, r;
cin >> l >> r;
l--; r--;
cout << (r + 1 <= rightp[l] ? "YES" : "NO") << "\n";
}
return 0;
}
Compilation message
Joker.cpp: In constructor 'UF::UF(ll)':
Joker.cpp:41:5: warning: 'UF::parity' will be initialized after [-Wreorder]
41 | vi parity;
| ^~~~~~
Joker.cpp:40:5: warning: 'vi UF::par' [-Wreorder]
40 | vi par;
| ^~~
Joker.cpp:43:2: warning: when initialized here [-Wreorder]
43 | UF(int n) : size(n, 1), parity(n), par(n)
| ^~
Joker.cpp: In function 'void dc(ll, ll, ll, bool)':
Joker.cpp:130:6: warning: unused variable 'newhl' [-Wunused-variable]
130 | int newhl = newhr;
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
193 ms |
23112 KB |
Output is correct |
| 4 |
Correct |
282 ms |
23644 KB |
Output is correct |
| 5 |
Correct |
155 ms |
23392 KB |
Output is correct |
| 6 |
Correct |
217 ms |
20628 KB |
Output is correct |
| 7 |
Correct |
228 ms |
22016 KB |
Output is correct |
| 8 |
Correct |
286 ms |
20232 KB |
Output is correct |
| 9 |
Correct |
278 ms |
21980 KB |
Output is correct |
| 10 |
Correct |
305 ms |
25040 KB |
Output is correct |
| 11 |
Correct |
232 ms |
20656 KB |
Output is correct |
| 12 |
Correct |
251 ms |
22192 KB |
Output is correct |
| 13 |
Correct |
253 ms |
19996 KB |
Output is correct |
| 14 |
Correct |
273 ms |
19828 KB |
Output is correct |
| 15 |
Correct |
313 ms |
21828 KB |
Output is correct |
| 16 |
Correct |
329 ms |
24760 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
