| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1110060 | AverageAmogusEnjoyer | 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;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }
constexpr int nax = 200200,block_size = 450;
vector<pair<int,int>> queries[block_size][nax]; // r,idx
vector<bool> ans;
int edges[nax][2];
int n,m;
bool pref[nax];
bool suff[nax];
bool pref_suff[nax];
struct dsu_save {
int x,y,lzx,lzy,szx,szy,parx,pary;
};
struct DSU {
int lz[nax];
int par[nax];
int sz[nax];
dsu_save stk[nax]; // avoid allocating a lot of memory on heap -- better to allocate initially on stack
int T = 0;
void init() {
for (int i = 0; i < nax; i++)
lz[i] = 0, par[i] = i, sz[i] = 1;
}
int get(int x,int &cx) {
while(1) {
cx ^= lz[x];
if (x == par[x])
return x;
x = par[x];
}
}
bool need_reset = 0;
bool unite(int x,int y) {
assert(!need_reset);
int cx = 0,cy = 0;
int px = get(x,cx), py = get(y,cy);
if (sz[px] < sz[py])
swap(px,py), swap(cx,cy);
stk[T++] = {px,py,lz[px],lz[py],sz[px],sz[py],par[px],par[py]};
if (cx == cy) {
if (px == py) {
need_reset = 1;
return 1;
} else {
lz[py] ^= 1;
sz[px] += sz[py];
par[py] = px;
}
} else {
if (px != py) {
sz[px] += sz[py];
par[py] = px;
}
}
return 0;
}
void rollback(int k) {
need_reset = 0;
assert(T >= k);
while(k--) {
auto &c = stk[--T];
lz[c.x] = c.lzx,lz[c.y] = c.lzy,par[c.x] = c.parx,par[c.y] = c.pary,sz[c.x] = c.szx,sz[c.y] = c.szy;
}
}
};
DSU dsu;
bool solve_block(int block) {
int current_r = m - 1;
for (int i = max(0,(block - 1) * block_size); i < min(m,block * block_size); i++) {
if (dsu.unite(edges[i][0],edges[i][1])) {
for (int B = block; B < block_size; B++)
for (int r = block * block_size; r <= m; r++)
for (auto &[l,idx]: queries[B][r])
ans[idx] = 1;
return 1;
}
}
for (int r = m; r >= block * block_size; r--) {
for (int i = 0, K = 0; i < queries[block][r].size();) {
auto &[l,idx] = queries[block][r][i];
while(K < queries[block][r].size() && queries[block][r][K].first == l) K++;
bool RW = 0;
if (pref[l] || suff[m - r] || pref_suff[min(l,m - r)]) {
RW = 1;
} else {
while(current_r >= r) {
if (dsu.unite(edges[current_r][0],edges[current_r][1])) {
for (int j = i; j < queries[block][r].size(); j++) {
int idx2 = queries[block][r][j].second;
ans[idx2] = 1;
}
dsu.rollback(m - current_r); // potrebbero essere necessari dei +- 1
return 0;
}
current_r--;
}
--l;
int inserted = 0;
while(l >= block * block_size) {
// devo inserirlo
inserted++;
// cout << "edge index: " << l + 1 << endl;
if (dsu.unite(edges[l][0],edges[l][1])) {
RW = 1;
break;
}
l--;
}
dsu.rollback(inserted);
}
while(i < K) {
ans[queries[block][r][i].second] = RW;
i++;
}
}
}
dsu.rollback(m - current_r - 1);
return 0;
}
bool res[block_size][block_size];
void precomp() {
dsu.init();
for (int block = 0; block < block_size; block++) {
bool flag = 0;
int ins = 0;
for (int other = block_size - 1; other > block && !flag; other--) {
int l = other * block_size; // questo e' acceso!
int r = min(m,(other + 1) * block_size);
--r;
while(r >= l) {
ins++;
if (dsu.unite(edges[r][0],edges[r][1])) {
for (int O = other; O > block; O--)
res[block][O] = 1;
flag = 1;
dsu.rollback(ins);
ins = 0;
break;
}
r--;
}
}
dsu.rollback(ins);
assert(dsu.T == min(m,block * block_size));
for (int i = block_size * block; i < (block + 1) * block_size && i < m; i++) {
if (dsu.unite(edges[i][0],edges[i][1])) {
for (int BL = block + 1; BL < block_size; BL++)
for (int BR = BL + 1; BR < block_size; BR++)
res[BL][BR] = 1;
dsu.rollback(i + 1);
assert(dsu.T == 0);
return;
}
}
}
assert(dsu.T == m);
dsu.rollback(m);
}
bool FOUND_GLOBAL = 0;
void precomp2() {
dsu.init();
int i = 1;
while(i <= m && !dsu.unite(edges[i - 1][0],edges[i - 1][1])) i++;
FOUND_GLOBAL = (i != m + 1);
if (!FOUND_GLOBAL) {
dsu.rollback(m);
return;
}
dsu.rollback(i);
while(i <= m)
pref[i++] = 1;
i = 1;
while(i <= m && !dsu.unite(edges[m - i][0],edges[m - i][1])) i++;
dsu.rollback(i);
assert(dsu.T == 0);
while(i <= m)
suff[i++] = 1;
int l = 0, r = m - 1;
int p = 0;
bool f = 0;
while(l < r) {
p++;
if (dsu.unite(edges[l][0],edges[l][1])) {
f = 1;
break;
}
p++;
if (dsu.unite(edges[r][0],edges[r][1])) {
f = 1;
break;
}
l++,r--;
}
dsu.rollback(p);
assert(dsu.T == 0);
p = (p + 1) / 2;
while(p <= m)
pref_suff[p++] = f;
}
vector<bool> trova_cicli(int N, int M, int Q, vector<int> A, vector<int> B, vector<int> L, vector<int> R) {
n = N, m = M;
for (int i = 0; i < M; i++)
edges[i][0] = A[i],edges[i][1] = B[i];
// precomp(); too slow for now
precomp2();
dsu.init();
ans.resize(Q);
if (!FOUND_GLOBAL)
return ans;
for (int i = 0; i < Q; i++)
queries[L[i] / block_size][R[i]].emplace_back(L[i],i);
for (int i = 0; i < block_size; i++)
if (solve_block(i))
break;
return ans;
}
int main() {
int N,M,Q;
cin >> N >> M >> Q;
vector<int> A(M),B(M),L(Q),R(Q);
for (int i = 0; i < M; i++) {
cin >> A[i] >> B[i];
--A[i],--B[i];
}
for (int i = 0; i < Q; i++) {
cin >> L[i] >> R[i];
--L[i];
}
auto risposta = trova_cicli(N,M,Q,A,B,L,R);
for (int i = 0; i < Q; i++)
cout << (risposta[i] ? "YES" : "NO") << "\n";
}