| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 678734 |
2023-01-06T13:04:12 Z |
elkernos |
Joker (BOI20_joker) |
C++17 |
|
342 ms |
12536 KB |
// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x) \
sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
{
sim > struct rge {
c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
~debug()
{
cerr << endl;
}
eni(!=) cerr << boolalpha << i;
ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
*this << "[";
for (auto it = d.b; it != d.e; ++it)
*this << ", " + 2 * (it == d.b) << *it;
ris << "]";
}
#else
sim dor(const c &)
{
ris;
}
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#ifdef XOX
#warning Times may differ!!!
#endif
#define endl '\n'
#define pb emplace_back
#define vt vector
#define rep(i, a, b) for (int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int nax = 1000 * 1007, mod = 1e9 + 7;
struct RollbackUF {
vt<int> e;
vt<pii> st;
RollbackUF(int n) : e(n, -1) {}
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : find(e[x]); }
int time() { return sz(st); }
void rollback(int t)
{
for (int i = time(); i-- > t;)
e[st[i].first] = st[i].second;
st.resize(t);
}
bool join(int a, int b)
{
a = find(a), b = find(b);
if (a == b) return false;
if (e[a] > e[b]) swap(a, b);
st.pb(a, e[a]);
st.pb(b, e[b]);
e[a] += e[b];
e[b] = a;
return true;
}
};
int main()
{
cin.tie(0)->sync_with_stdio(0);
int n, m, q;
cin >> n >> m >> q;
vt<pii> edges(m);
for (auto &[a, b] : edges) {
cin >> a >> b;
}
RollbackUF uf(2 * n + 12);
vt<int> last(m);
auto lacz = [&](int i) {
if (i == m) {
return;
}
uf.join(edges[i].first, edges[i].second + n);
uf.join(edges[i].first + n, edges[i].second);
};
auto same = [&](int i) {
if (i == m) {
return false;
}
return uf.find(edges[i].first) == uf.find(edges[i].first + n);
};
function<void(int, int, int, int)> rek = [&](int l, int r, int a, int b) {
int mid = (l + r) / 2;
int t1 = uf.time();
for (int i = l; i < mid; i++) {
lacz(i);
if (same(i)) {
last[mid] = m;
break;
}
}
int t2 = uf.time();
for (int i = b; i >= max(mid, a); i--) {
lacz(i);
if (same(i)) {
last[mid] = i;
break;
}
}
uf.rollback(t2);
if (mid < r) {
lacz(mid);
rek(mid + 1, r, max(mid + 1, last[mid]), b);
}
uf.rollback(t1);
if (l < mid) {
int t3 = uf.time();
for (int i = b; i > last[mid]; i--) {
lacz(i);
}
rek(l, mid - 1, a, last[mid]);
uf.rollback(t3);
}
};
rek(0, m - 1, 0, m - 1);
debug() << imie(last);
while (q--) {
int a, b;
cin >> a >> b;
a--, b--;
cout << (last[a] <= b ? "NO" : "YES") << endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
219 ms |
7700 KB |
Output is correct |
| 4 |
Correct |
208 ms |
12536 KB |
Output is correct |
| 5 |
Correct |
175 ms |
12352 KB |
Output is correct |
| 6 |
Correct |
152 ms |
7628 KB |
Output is correct |
| 7 |
Correct |
165 ms |
7640 KB |
Output is correct |
| 8 |
Correct |
194 ms |
5840 KB |
Output is correct |
| 9 |
Correct |
212 ms |
7620 KB |
Output is correct |
| 10 |
Correct |
342 ms |
12500 KB |
Output is correct |
| 11 |
Correct |
219 ms |
7588 KB |
Output is correct |
| 12 |
Correct |
318 ms |
12372 KB |
Output is correct |
| 13 |
Correct |
198 ms |
4188 KB |
Output is correct |
| 14 |
Correct |
187 ms |
5648 KB |
Output is correct |
| 15 |
Correct |
267 ms |
7904 KB |
Output is correct |
| 16 |
Correct |
340 ms |
12508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
