#include <bits/stdc++.h>
using namespace std;
struct DSU
{
vector<int> rt, sz;
vector<int> stk;
DSU(int n)
{
rt.resize(n);
iota(rt.begin(), rt.end(), 0);
sz.resize(n, 1);
}
int find(int u)
{
if (u == rt[u])
{
return u;
}
return find(rt[u]);
}
bool same(int u, int v)
{
return find(u) == find(v);
}
void unite(int u, int v)
{
u = find(u), v = find(v);
if (u == v)
{
stk.push_back(-1);
return;
}
if (sz[u] > sz[v])
{
swap(u, v);
}
rt[u] = v;
sz[v] += sz[u];
stk.push_back(u);
}
void undo()
{
int u = stk.back();
stk.pop_back();
if (u == -1)
{
return;
}
int v = rt[u];
sz[v] -= sz[u];
rt[u] = u;
}
};
const int B = 3, C = 3, D = 1;
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, m, q;
cin >> n >> m >> q;
vector<pair<int, int>> ed(m);
for (int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
u--, v--;
ed[i] = make_pair(u, v);
}
vector<int> rr(m, -1);
for (int c = 0; c * C * B < m; c++)
{
int L1 = c * C * B, L2 = min(m, (c + 1) * C * B);
int R = -1;
DSU dsu(2 * n);
{
for (int i = 0; i < L1; i++)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
if (dsu.same(u, v))
{
R = i;
break;
}
}
if (R != -1)
{
break;
}
for (int i = L1; i < L2; i++)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
if (dsu.same(u, v))
{
R = i;
break;
}
}
if (R == -1)
{
R = m - 1;
while (R >= L2)
{
auto [u, v] = ed[R];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
if (dsu.same(u, v))
{
dsu.undo();
dsu.undo();
break;
}
R--;
}
for (int i = m - 1; i > R; i--)
{
dsu.undo();
dsu.undo();
}
for (int i = L1; i < L2; i++)
{
dsu.undo();
dsu.undo();
}
}
else
{
for (int i = L1; i <= R; i++)
{
dsu.undo();
dsu.undo();
}
R = m - 1;
}
for (int i = m - 1; i > R; i--)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
}
}
for (int d = (L2 - 1 - L1) / (B * D); d >= 0; d--)
{
int ll = L1 + d * B * D;
for (int i = L1; i < ll; i++)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
}
for (int i = ll; i < L2; i++)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
}
int r2 = R;
for (int b = (L2 - 1 - ll) / B; b >= 0; b--)
{
int l1 = ll + b * B, l2 = min(L2, l1 + B);
for (int i = l1; i < l2; i++)
{
dsu.undo();
dsu.undo();
}
for (int i = R; i > r2; i--)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
}
int r = r2;
bool f = 0;
for (int i = r; i >= l1; i--)
{
int l = l1;
while (l < l2 && l <= i)
{
auto [u, v] = ed[l];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
if (dsu.same(u, v))
{
break;
}
l++;
}
rr[i] = l;
l = min(l, l2 - 1);
l = min(l, i);
for (int j = l1; j <= l; j++)
{
dsu.undo();
dsu.undo();
}
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
if (dsu.same(u, v))
{
r2 = i;
f = 1;
break;
}
}
if (!f)
{
r2 = l1;
}
for (int i = r2; i <= R; i++)
{
dsu.undo();
dsu.undo();
}
}
for (int i = L1; i < ll; i++)
{
dsu.undo();
dsu.undo();
}
for (int i = r2 + 1; i <= R; i++)
{
auto [u, v] = ed[i];
dsu.unite(u, v + n);
dsu.unite(u + n, v);
}
R = r2;
}
}
while (q--)
{
int l, r;
cin >> l >> r;
l--, r--;
cout << (rr[r] >= l ? "NO" : "YES") << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Execution timed out |
2076 ms |
8128 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
756 KB |
Output is correct |
| 3 |
Correct |
1 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
348 KB |
Output is correct |
| 5 |
Correct |
0 ms |
348 KB |
Output is correct |
| 6 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
