#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pw(x) (1LL << (x))
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umx(T& a, T b) {
return a < b ? a = b, 1 : 0;
}
template <typename T>
bool umn(T& a, T b) {
return a > b ? a = b, 1 : 0;
}
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 4e5 + 5;
int n, m, q;
ve<pii> e;
int ans[N];
int link[N];
ve<int> g[N];
int root(int x) {
if (link[x] == x) {
return x;
} else {
return link[x] = root(link[x]);
}
}
bool uni(int a, int b) {
a = root(a);
b = root(b);
if (a == b) {
return 0;
}
link[a] = b;
return 1;
}
int dep[N];
int up[N][20];
int tin[N], tout[N], timer;
int vis[N];
ve<pii> ask[N];
void dfs(int v, int p) {
vis[v] = 1;
tin[v] = timer++;
up[v][0] = p;
fr (i, 1, 19) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
fe (to, g[v]) {
if (to == p) continue;
dep[to] = dep[v] + 1;
dfs(to, v);
}
tout[v] = timer;
}
bool isUpper(int a, int b) {
return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int getLCA(int a, int b) {
if (isUpper(a, b)) return a;
if (isUpper(b, a)) return b;
rf (i, 19, 0) {
if (up[a][i] && !isUpper(up[a][i], b)) {
a = up[a][i];
}
}
return up[a][0];
}
int getDist(int a, int b) {
int c = getLCA(a, b);
return dep[a] + dep[b] - 2 * dep[c];
}
bool found;
int l, r;
ve<pii> G[N];
void DFS(int v, int p) {
vis[v] = 1;
fe (to, G[v]) {
if (to.fi == p) continue;
if (to.se >= l && to.se <= r) continue;
if (!vis[to.fi]) {
dep[to.fi] = dep[v] + 1;
DFS(to.fi, v);
} else {
if (vis[to.fi] == 2) {
found |= (dep[v] - dep[to.fi]) % 2 == 0;
}
}
}
vis[v] = 2;
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
//
cout << 2e5 * 200 / 1e8 << "\n";
//
return 0;
cin >> n >> m >> q;
fr (i, 1, m) {
int a, b;
cin >> a >> b;
e.pb({a, b});
G[a].pb({b, i - 1});
G[b].pb({a, i - 1});
}
fr (i, 0, m - 1) {
e.pb(e[i]);
}
if (q <= 2000) {
fr (i, 1, q) {
cin >> l >> r;
l--;
r--;
// r+1..m-1+l
found = 0;
fill(vis + 1, vis + 1 + n, 0);
fr (v, 1, n) {
if (!vis[v]) {
dep[v] = 0;
DFS(v, 0);
}
}
ask[m - 1 + l].pb({r + 1, i});
if (found) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
fr (i, 1, q) {
cin >> l >> r;
l--;
r--;
// r+1..m-1+l
// found = 0;
// fill(vis + 1, vis + 1 + n, 0);
// fr (v, 1, n) {
// if (!vis[v]) {
// dep[v] = 0;
// DFS(v, 0);
// }
// }
if (l == 0 && r == m - 1) {
ans[i] = 0;
} else {
ask[m - 1 + l].pb({r + 1, i});
}
// if (found) {
// cout << "YES\n";
// } else {
// cout << "NO\n";
// }
}
// return 0;
fr (i, 0, sz(e) - 1) {
if (sz(ask[i])) {
sort(all(ask[i]));
reverse(all(ask[i]));
iota(link, link + n + 1, 0);
fr (j, 1, n) g[j].clear();
rf (j, i, 0) {
if (uni(e[j].fi, e[j].se)) {
g[e[j].fi].pb(e[j].se);
g[e[j].se].pb(e[j].fi);
}
}
fr (v, 1, n) {
fr (p, 0, 19) {
up[v][p] = 0;
}
}
fill(vis + 1, vis + 1 + n, 0);
fr (v, 1, n) {
if (!vis[v]) {
timer = 0;
dep[v] = 0;
dfs(v, 0);
}
}
iota(link, link + n + 1, 0);
bool ok = 0;
int ptr = 0;
rf (j, i, 0) {
if (uni(e[j].fi, e[j].se)) {
} else {
if (!ok) {
int d = getDist(e[j].fi, e[j].se);
if (d % 2 == 0) {
ok = 1;
}
}
}
while (ptr < sz(ask[i]) && ask[i][ptr].fi == j) {
ans[ask[i][ptr].se] = ok;
ptr++;
}
}
}
}
fr (i, 1, q) {
if (ans[i]) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
18 ms |
28508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
