| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 925894 |
2024-02-12T10:29:24 Z |
vjudge1 |
Joker (BOI20_joker) |
C++17 |
|
0 ms |
0 KB |
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")
#include<bits/stdc++.h>
using namespace std;
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define sz(a) (int)a.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<pii> rid = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
vector<pii> dir = {{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
const int N = 4e5 + 1, mod = 998244353;
const ll inf = 1e9;
double eps = 1e-15;
bool flg = 0;
const int k = 1000;
bool ok = 1, was[N];
vector<pii> g(N);
int p[N + 1], pr[N];
int sz[N + 1], pt[N + 1];
vector<array<int, 2>> h;
pii get(int x) {
if (p[x] == x) return {x, 0};
pii val = get(p[x]);
return {val.f, (pr[x] + val.s) % 2};
}
void add(int id) {
int u = g[id].f;
int v = g[id].s;
pii x = get(u);
pii y = get(v);
if (x.f == y.f) {
if (x.s == y.s) {
if (ok) {
h.push_back({-1, -1});
ok = 0;
}
}
return;
}
if (sz[x.f] > sz[y.f]) swap(x, y);
h.push_back({x.f, sz[x.f]});
h.push_back({y.f, sz[y.f]});
p[x.f] = y.f;
pr[x.f] = (x.s + y.s + 1) % 2;
sz[y.f] += sz[x.f];
}
void rb() {
while (sz(h) && !pt[sz(h)]) {
array<int, 2> x = h.back();
h.pop_back();
if (x[0] == -1) {
ok = 1;
continue;
}
p[x[0]] = x[0];
pr[x[0]] = 0;
sz[x[0]] = x[1];
}
pt[sz(h)] = 0;
}
bool slave(int l, int r) {
for (int i = l; i <= r; i++) add(i);
bool vv = ok;
rb();
return vv;
}
bool cmp(array<int, 3> a, array<int, 3> b) {
if (a[0] / k < b[0] / k) return 1;
if (a[0] / k == b[0] / k && a[1] < b[1]) return 1;
return 0;
}
void slv() {
int n, m, q;
cin >> n >> m >> q;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[i] = g[i + m] = {u, v};
}
for (int i = 1; i <= n; i++)
p[i] = i, sz[i] = 1;
if (q > 2000) {
vector<pii> qr[201];
bool ans[q + 1];
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
qr[l].push_back({r + 1, i});
}
for (int l = 1; l <= min(m, 200); l++) {
for (int j = 1; j <= n; j++)
p[j] = j, sz[j] = 1;
for (int j = 1; j < l; j++) add(j);
int p = m + 1;
for (auto [r, id]: qr) {
while (p > r)
add(--p);
ans[id] = ok;
}
}
for (int i = 1; i <= q; i++) {
if (ans[i]) cout << "NO\n";
else cout << "YES\n";
}
return;
}
vector<array<int, 3>> qr;
bool ans[q + 1];
for (int i = 1; i <= q; i++) {
int l, r;
cin >> l >> r;
int tl = r + 1, tr = l + m - 1;
if (tl / k == tr / k)
ans[i] = slave(tl, tr);
else qr.push_back({tl, tr, i});
}
sort(all(qr), cmp);
int tr = 0, lst = -1, pos;
for (auto [l, r, id]: qr) {
if (l / k != lst) {
rb();
lst = l / k;
pos = (lst + 1) * k - 1;
tr = pos;
}
while (tr < r)
add(++tr);
pt[sz(h)] = 1;
for (int i = pos; i >= l; i--)
add(i);
ans[id] = ok;
rb();
}
for (int i = 1; i <= q; i++) {
if (ans[i]) cout << "NO\n";
else cout << "YES\n";
}
}
main() {
//freopen("rsq.in", "r", stdin);
//freopen("rsq.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
int tp = 1;
if (flg) cin >> tp;
while (tp--) {
slv();
}
}
//wenomechainsama
Compilation message
Joker.cpp: In function 'void slv()':
Joker.cpp:119:14: error: 2 names provided for structured binding
119 | for (auto [r, id]: qr) {
| ^~~~~~~
Joker.cpp:119:14: note: while 'std::vector<std::pair<int, int> >' decomposes into 1 element
Joker.cpp: At global scope:
Joker.cpp:165:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
165 | main() {
| ^~~~
