| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 384356 | LinusTorvaldsFan | Joker (BOI20_joker) | C++14 | 0 ms | 0 KiB |
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 optimize("Ofast")
#include <iostream>
#include <string.h>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <assert.h>
#include <cmath>
#include <memory.h>
#include <queue>
#include <bitset>
#include <set>
using namespace std;
#define rep(i, n) for(int i =0;i<(n);i++)
#define per(i, n) for (int i=((int)n-1);i>=0;i--)
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
#define make_unique(x) { sort(all(x)); x.resize(unique(x.begin(), x.end()) - x.begin()); }
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define add insert
#define debug(x) { cerr << #x << "= " << x << "\n"; }
typedef long long ll;
typedef vector<int>vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
typedef pair<ll, ll> pll;
typedef vector<string> vs;
const int N = 200100;
int dsu[2 * N];
int sz[2 * N];
bool is_bipar = true;
vector<tuple<int, int, int, int>> ba;
vector<bool> bipar;
inline int find(int x) {
while (x != dsu[x]) x = dsu[x];
return x;
}
inline void unite(int a, int b) {
a = find(a);
b = find(b);
if (sz[a] < sz[b]) swap(a, b);
if (a == b) return;
bipar.pb(is_bipar);
ba.eb(a, sz[a], b, dsu[b]);
dsu[b] = a;
sz[a] += sz[b];
}
bool same(int a, int b) {
return find(a) == find(b);
}
void merge(int a, int b) {
unite(a, b + N);
unite(b, a + N);
if (same(a, a + N) || same(b, b + N)) {
is_bipar = false;
}
}
void back() {
int a, b, c, d;
tie(a, b, c, d) = ba.back();
sz[a] = b;
dsu[c] = d;
is_bipar = bipar.back();
ba.pop_back();
bipar.pop_back();
}
void init() {
rep(i, 2 * N) {
dsu[i] = i;
sz[i] = 1;
}
}
bool ans[N];
struct Q {
int l, r, i;
};
bool operator<(Q a, Q b) {
return a.r > b.r;
}
vector<Q> qu[N];
int main() {
bipar.reserve(2 * N);
ba.reserve(2 * N);
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
vpii edges;
rep(i, m) {
int u, v;
cin >> u >> v;
edges.eb(u, v);
}
const int K = 400;
rep(i, q) {
int l, r;
cin >> l >> r;
l--; r--;
qu[l / K].pb({ l, r, i });
}
init();
rep(bl, N) {
if (qu[bl].size()) {
sort(all(qu[bl]));
int bl_l = bl * K;
int bl_r = min((bl + 1) * K - 1, m - 1);
int pr = m - 1;
int was_on_start = ba.size();
rep(j, sz(qu[bl])) {
while (pr > qu[bl][j].r) {
int v1 = edges[pr].ff;
int v2 = edges[pr].ss;
pr--;
merge(v1, v2);
}
int was = ba.size();
for (int i = qu[bl][j].l - 1; i >= bl_l; i--) {
int v1 = edges[i].ff;
int v2 = edges[i].ss;
merge(v1, v2);
}
ans[qu[bl][j].i] = is_bipar;
while (ba.size() != was) {
back();
}
}
}
while (ba.size() != was_on_start) {
back();
}
for (int i = bl_l; i <= bl_r; i++) {
int v1 = edges[i].ff;
int v2 = edges[i].ss;
merge(v1, v2);
}
}
rep(i, q) {
if (ans[i]) cout << "NO\n";
else cout << "YES\n";
}
return 0;
}