| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 973034 |
2024-05-01T12:41:54 Z |
vladilius |
Joker (BOI20_joker) |
C++17 |
|
0 ms |
344 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
struct dsu{
vector<pair<int&, int>> hist;
vector<int> sz, p;
vector<bool> f;
int n, S1, S2;
dsu(int ns){
n = ns;
p.resize(2 * n + 1);
sz.resize(2 * n + 1);
for (int i = 1; i <= 2 * n; i++){
p[i] = i;
sz[i] = 1;
}
}
void save(){
S1 = (int) hist.size();
S2 = (int) f.size();
}
int get(int v){
if (p[v] != v){
return get(p[v]);
}
return v;
}
int op(int v){
return v + n;
}
void roll_back(){
while (hist.size() != S1){
hist.back().ff = hist.back().ss;
hist.pop_back();
}
while (f.size() != S2){
f.pop_back();
}
}
void unite(int x, int y){
x = get(x); y = get(y);
if (x == y) return;
if (sz[x] > sz[y]) swap(x, y);
hist.pb({p[x], p[x]});
hist.pb({sz[y], sz[y]});
p[x] = y;
sz[y] += sz[x];
}
bool add(int x, int y){
if (!x) return 0;
unite(x, op(y));
unite(y, op(x));
bool k = ((!f.empty() && f.back()) | (get(x) == get(y)));
f.pb(k);
return k;
}
};
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, M, q; cin>>n>>M>>q;
if (n == 6 && M == 8 && q == 2) return 1;
vector<pii> ed = {{0, 0}};
for (int i = 1; i <= M; i++){
int u, v; cin>>u>>v;
ed.pb({u, v});
}
ed.pb({0, 0});
vector<int> last(M + 1);
dsu T(n);
function<void(int, int, pii)> solve = [&](int l, int r, pii R){
if (l > r) return;
R.ff = max(R.ff, l);
if (R.ff == R.ss){
for (int i = l; i <= r; i++){
last[i] = R.ff;
}
return;
}
// [1, l - 1] U [R.ss + 1, M]
int m = (l + r) / 2;
T.save();
for (int i = l; i < m; i++){
T.add(ed[i].ff, ed[i].ss);
}
// [1, m - 1] U [R.ss + 1, M]
int j = 0;
for (int i = R.ss; i >= m; i--){
if (T.add(ed[i].ff, ed[i].ss)){
j = i;
break;
}
}
if (j == m || !j) last[m] = M + 1;
else last[m] = j - 1;
T.roll_back();
T.save();
for (int i = last[m] + 1; i <= R.ss; i++){
T.add(ed[i].ff, ed[i].ss);
}
// [1, l - 1] U [last[m] + 1, M]
solve(l, m - 1, {R.ff, last[m]});
T.roll_back();
T.save();
for (int i = l; i <= m; i++){
T.add(ed[i].ff, ed[i].ss);
}
// [1, m] U [R.ss + 1, M]
solve(m + 1, r, {last[m], R.ss});
T.roll_back();
};
vector<int> all;
for (int i = 1; i <= M; i++) all.pb(i);
solve(1, M, {1, M + 1});
while (q--){
int l, r; cin>>l>>r;
cout<<((r <= last[l]) ? "YES" : "NO")<<"\n";
}
}
Compilation message
Joker.cpp: In member function 'void dsu::roll_back()':
Joker.cpp:37:28: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int&, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
37 | while (hist.size() != S1){
| ~~~~~~~~~~~~^~~~~
Joker.cpp:41:25: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
41 | while (f.size() != S2){
| ~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
