| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 858300 | Trisanu_Das | Joker (BOI20_joker) | C++17 | 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.
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
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() {
for(int i = 0; i < 2 * N; i++) {
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;
for(int i = 0; i < m ; i++){
int u, v;
cin >> u >> v;
edges.pb(u, v);
}
const int K = 2000;
for(int i = 0; i < q; i++){
int l, r;
cin >> l >> r;
l--; r--;
qu[l / K].pb({ l, r, i });
}
init();
for(int bl = 0; bl < N; bl++){
int bl_l = bl * K;
int bl_r = min((bl + 1) * K - 1, m - 1);
if (qu[bl].size()) {
sort(qu[bl].begin, qu[bl].end());
int pr = m - 1;
int was_on_start = ba.size();
for(int j = 0; j < qu[bl.size(); j++){
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);
}
}
for(int i = 0; i < q; i++){
if (ans[i]) cout << "NO\n";
else cout << "YES\n";
}
}