| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 689320 | zeroesandones | 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;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pi;
#define FOR(i, j, k) for (ll i = j; i < (ll) k; ++i)
#define FORD(i, j, k) for (ll i = j; i >= (ll) k; --i)
#define nl "\n"
#define sp " "
#define all(x) (x).begin(), (x).end()
#define sc second
#define fr first
#define pb emplace_back
struct UFDS {
vi link, sz, len;
int n;
UFDS(int N) {
init(N);
}
void init(int N) {
n = N;
link = vi(n);
iota(all(link), 0);
sz = vi(n, 1);
len = vi(n, 0);
}
pi find(ll x) {
if(link[x] == x)
return {x, 0};
pi val = find(link[x]);
link[x] = val.fr;
len[x] = (len[x] + val.sc) % 2;
return {link[x], len[x]};
}
void unite(ll a, ll b) {
pi A = find(a);
pi B = find(b);
if(A.fr == B.fr) return;
if(sz[A.fr] < sz[B.fr]) swap(A, B);
link[B.fr] = A.fr;
len[B.fr] = (1 + A.sc + B.sc) % 2;
sz[A.fr] += sz[B.fr];
}
bool same(ll a, ll b){
return (find(a) == find(b));
}
};
void solve()
{
ll n, m, q;
cin >> n >> m >> q;
vector<pi> e(m + 1);
FOR(i, 1, m + 1) {
cin >> e[i].fr >> e[i].sc;
}
UFDS uf(n + 1);
vector<pi> query[201];
FOR(i, 0, q) {
ll l, r;
cin >> l >> r;
query[l].pb(r, i);
}
vector<bool> ans(q, false);
FOR(i, 0, 201) {
sort(all(query[i]), [&](pi x, pi y) {
return x.fr > y.fr;
});
}
FOR(T, 1, 201) {
bool cyc = false;
uf.init(n + 1);
FOR(i, 1, min(T + 1, m + 1)) {
if(uf.same(e[i].fr, e[i].sc)) {
pi A = uf.find(e[i].fr);
pi B = uf.find(e[i].sc);
if(A.sc == B.sc) {
cyc = true;
}
} else {
uf.unite(e[i].fr, e[i].sc);
}
}
ll r = m;
for(auto i : query[T]) {
while(r > i.fr) {
if(uf.same(e[r].fr, e[r].sc)) {
pi A = uf.find(e[r].fr);
pi B = uf.find(e[r].sc);
if(A.sc == B.sc) {
cyc = true;
}
} else {
uf.unite(e[r].fr, e[r].sc);
}
--r;
}
ans[i.sc] = cyc;
}
}
for(auto i : ans) {
cout << (i ? "YES" : "NO") << nl;
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t = 1;
// cin >> t;
while (t--)
{
solve();
}
}