| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 699245 |
2023-02-16T08:52:40 Z |
maomao90 |
Joker (BOI20_joker) |
C++17 |
|
230 ms |
16440 KB |
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 200005;
int n, m, q;
int u[MAXN], v[MAXN];
vii ql[MAXN];
int mnr[MAXN];
bool ans[MAXN];
int p[MAXN], rnk[MAXN];
bool col[MAXN];
viii undostk;
void init() {
undostk.clear();
REP (i, 1, n + 1) {
p[i] = i;
rnk[i] = 1;
col[i] = 0;
}
}
ii findp(int u) {
if (p[u] == u) {
return {u, 0};
}
auto [tp, c] = findp(p[u]);
return {tp, c ^ col[u]};
}
bool join(int a, int b) {
auto [pa, ca] = findp(a);
auto [pb, cb] = findp(b);
if (pa == pb) {
if (ca == cb) {
return 0;
}
undostk.pb({-1, -1, -1});
return 1;
}
if (rnk[pa] < rnk[pb]) {
swap(pa, pb);
}
bool delta = 0;
if (rnk[pa] == rnk[pb]) {
delta = 1;
rnk[pa]++;
}
undostk.pb({pa, pb, delta});
p[pb] = pa;
col[pb] = ca == cb;
return 1;
}
void undo() {
assert(!undostk.empty());
auto [pa, pb, delta] = undostk.back(); undostk.pop_back();
if (pa == -1) {
return;
}
p[pb] = pb;
col[pb] = 0;
rnk[pa] -= delta;
}
int ti, ptr;
vii stk;
bool push(int i) {
bool res = join(u[i], v[i]);
if (res) {
stk.pb({i, ++ptr});
}
return res;
}
void pop_front() {
vii astk, bstk;
while (!stk.empty()) {
ii x = stk.back(); stk.pop_back();
if (x.SE <= ti) {
astk.pb(x);
} else {
bstk.pb(x);
}
if (SZ(astk) >= SZ(bstk) * 2) {
break;
}
}
REP (i, 0, SZ(astk) + SZ(bstk)) {
undo();
}
if (SZ(astk) == 0) {
ti = bstk[0].SE;
REP (z, 0, SZ(bstk) - 1) {
ii i = bstk[z];
stk.pb(i);
join(u[i.FI], v[i.FI]);
}
cerr << " - " << bstk.back().FI << ' ' << bstk.back().SE << '\n';
return;
}
while (!bstk.empty()) {
ii i = bstk.back(); bstk.pop_back();
join(u[i.FI], v[i.FI]);
stk.pb(i);
}
while (SZ(astk) > 1) {
ii i = astk.back(); astk.pop_back();
join(u[i.FI], v[i.FI]);
stk.pb(i);
}
cerr << " - " << astk.back().FI << ' ' << astk.back().SE << '\n';
}
int main() {
#ifndef DEBUG
ios::sync_with_stdio(0), cin.tie(0);
#endif
cin >> n >> m >> q;
REP (i, 1, m + 1) {
cin >> u[i] >> v[i];
}
REP (i, 0, q) {
int l, r; cin >> l >> r;
ql[l].pb({r, i});
/*
while (!undostk.empty()) {
undo();
}
bool pos = 1;
REP (j, 1, l) {
if (!join(u[j], v[j])) {
pos = 0;
break;
}
}
if (!pos) {
cout << "YES\n";
continue;
}
REP (j, r + 1, m + 1) {
if (!join(u[j], v[j])) {
pos = 0;
break;
}
}
if (!pos) {
cout << "YES\n";
continue;
}
cout << "NO\n";
*/
}
init();
int sr = 1;
RREP (l, m, 1) {
if (!join(u[l], v[l])) {
sr = l + 1;
break;
}
}
init();
cerr << sr << '\n';
REP (i, sr, m + 1) {
assert(push(i));
}
mnr[1] = sr;
int r = sr;
REP (l, 2, m + 1) {
while (r <= m + 1 && !push(l - 1)) {
pop_front();
r++;
}
cerr << ' ' << l << ' ' << r << '\n';
mnr[l] = r - 1;
}
REP (l, 1, m + 1) {
for (auto [r, i] : ql[l]) {
ans[i] = r >= mnr[l];
}
}
REP (i, 0, q) {
if (ans[i]) {
cout << "NO\n";
} else {
cout << "YES\n";
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Incorrect |
230 ms |
16440 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
2 ms |
4948 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
