| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1298869 | flo | Joker (BOI20_joker) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define task "testing"
#define ll long long
#define multitest 0
using namespace std;
struct Edge {
int u, v;
};
struct Queries {
int l, r;
};
const int N = 2e5;
int n, m, q;
Edge E[2*N+5];
Queries Q[N+5];
bitset<N+5> res;
namespace sub12 {
const int sN = 2e3;
int dsu[2*sN+5];
void reset() {
fill(dsu+1, dsu+2*n+1, -1);
}
int root(int v) {
return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
}
void unite(int u, int v) {
if ((u = root(u)) == (v = root(v))) return;
if (dsu[u] > dsu[v]) swap(u, v);
dsu[u] += dsu[v], dsu[v] = u;
}
bool connect(int u, int v) {
return root(u) == root(v);
}
bool check() {
return max({n, m, q}) <= sN;
}
bool qry(int l, int r) {
reset();
for (int x = l; x <= r; x++) {
unite(E[x].u, E[x].v+n);
unite(E[x].u+n, E[x].v);
}
for (int x = 1; x <= n; x++) {
if (connect(x, x+n)) return 1;
}
return 0;
}
void solve() {
for (int x = 1; x <= q; x++) {
if (qry(Q[x].r+1, Q[x].l+m-1)) res.set(x);
}
}
}
namespace sub34 {
const int L = 200;
int dsu[2*N+5], rt[L+5], mxL;
unordered_map<int, bool> st[2*N+5];
bool check() {
mxL = 0;
for (int x = 1; x <= q; x++) {
mxL = max(mxL, Q[x].l);
}
return mxL <= L;
}
int flip(int v) {
return v+(v <= n ? n : -n);
}
void reset() {
for (int x = 2*n; x >= 1; x--) {
dsu[x] = -1, st[x].clear(), st[x][x] = 1;
}
}
int root(int v) {
return dsu[v] < 0 ? v : dsu[v] = root(dsu[v]);
}
bool unite(int u, int v) {
if ((u = root(u)) == (v = root(v))) return 0;
if (dsu[u] > dsu[v]) swap(u, v);
dsu[u] += dsu[v], dsu[v] = u;
for (auto x : st[v]) {
if (st[u][flip(x)] == 1) return 1;
st[u][x] = 1;
}
st[v].clear();
return 0;
}
void calc(int l) {
reset();
bool ex = 0;
for (int x = 1; x < l && !ex; x++) {
ex |= unite(E[x].u, E[x].v+n);
ex |= unite(E[x].u+n, E[x].v);
}
if (ex) rt[l] = m+1;
for (int r = m; r > l && !ex; r--) {
ex |= unite(E[r].u, E[r].v+n);
ex |= unite(E[r].u+n, E[r].v);
if (ex) rt[l] = r;
}
}
void solve() {
for (int x = min(m, mxL); x >= 1; x--) calc(x);
for (int x = 1; x <= q; x++) {
if (Q[x].r < rt[Q[x].l]) res.set(x);
}
}
}
void flo(int ID) {
cin >> n >> m >> q;
for (int x = 1; x <= m; x++) {
cin >> E[x].u >> E[x].v;
E[x+m] = E[x];
}
for (int x = 1; x <= q; x++) {
cin >> Q[x].l >> Q[x].r;
}
if (sub12::check()) sub12::solve();
else if (sub34::check()) sub34::solve();
for (int x = 1; x <= q; x++) {
cout << (res.test(x) ? "YES\n" : "NO\n");
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
int TCS = 1, ID = 1;
if (multitest) {
cin >> TCS;
}
while (TCS--) flo(ID++);
return 0;
}