# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
764557 |
2023-06-23T15:01:53 Z |
MetalPower |
Joker (BOI20_joker) |
C++14 |
|
243 ms |
16352 KB |
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define fi first
#define se second
const int MX = 2e5 + 10;
// Let dp[l] be the maximum index such that removing [l, dp[l]) doesn't make the graph bipartite
// Observe that dp[i] <= dp[i + 1] <= dp[i + 2]
// Hence we can do a dnc-esque solution
// also to make the complexity much lower, we can do the 2-pointer cost usually used for dp-dnc
struct dsu{
int p[MX << 1], sz[MX << 1];
vector<pii> operations;
void init(){
for(int i = 0; i < (MX << 1); i++) p[i] = i, sz[i] = 1;
}
int f(int x){
if(p[x] == x) return x;
else return f(p[x]);
}
int Join(int u, int v){
int fu = f(u), fv = f(v);
if(fu == fv) return 0;
if(sz[fu] < sz[fv]){
operations.push_back({p[fu], fu});
p[fu] = fv;
operations.push_back({sz[fv], fv});
sz[fv] += sz[fu];
}else{
operations.push_back({p[fv], fv});
p[fv] = fu;
operations.push_back({sz[fu], fu});
sz[fu] += sz[fv];
}
return 1;
}
void rev(int x){
for(int i = 0; i < x; i++){
{
pii bk = operations.back();
sz[bk.se] = bk.fi;
operations.pop_back();
}
{
pii bk = operations.back();
p[bk.se] = bk.fi;
operations.pop_back();
}
}
}
bool con(int x){
return f(x * 2) == f(x * 2 + 1);
}
} D;
int N, M, Q;
vector<pii> edges;
int lf = 0, rg = -1, dp[MX];
void solve(int l, int r, int optl, int optr){
if(r < l) return;
// cout << "solve " << l << " " << r << '\n';
bool is_bipartite = true;
int op = 0;
int mid = l + r >> 1;
for(int i = l; i < mid; i++){
op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
if(D.con(edges[i].fi) || D.con(edges[i].se)){
dp[mid] = M; is_bipartite = false;
D.rev(op); op = 0;
break;
}
}
if(is_bipartite){
for(int i = optr; i >= optl && i >= mid; i--){
op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
if(D.con(edges[i].fi) || D.con(edges[i].se)){
dp[mid] = i;
D.rev(op); op = 0;
break;
}
}
for(int i = l; i <= mid; i++){
op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
}
solve(mid + 1, r, dp[mid], optr);
D.rev(op); op = 0;
} else {
for(int i = mid + 1; i <= r; i++) dp[i] = dp[mid];
}
for(int i = optr; i > dp[mid]; i--){
op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
}
solve(l, mid - 1, optl, dp[mid]);
D.rev(op); op = 0;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> M >> Q;
for(int i = 0; i < M; i++){
int u, v; cin >> u >> v;
edges.push_back({u, v});
}
edges.push_back({N + 1, N + 2});
D.init();
solve(0, M - 1, 0, M);
for(int i = 0; i < Q; i++){
int l, r; cin >> l >> r; l--, r--;
if(r < dp[l]) cout << "YES\n";
else cout << "NO\n";
}
}
Compilation message
Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
77 | int mid = l + r >> 1;
| ~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
190 ms |
13652 KB |
Output is correct |
4 |
Correct |
236 ms |
15948 KB |
Output is correct |
5 |
Correct |
195 ms |
16352 KB |
Output is correct |
6 |
Correct |
149 ms |
13632 KB |
Output is correct |
7 |
Correct |
153 ms |
13684 KB |
Output is correct |
8 |
Correct |
163 ms |
11824 KB |
Output is correct |
9 |
Correct |
178 ms |
12604 KB |
Output is correct |
10 |
Correct |
223 ms |
13460 KB |
Output is correct |
11 |
Correct |
180 ms |
13196 KB |
Output is correct |
12 |
Correct |
201 ms |
14160 KB |
Output is correct |
13 |
Correct |
166 ms |
11904 KB |
Output is correct |
14 |
Correct |
170 ms |
12308 KB |
Output is correct |
15 |
Correct |
243 ms |
13572 KB |
Output is correct |
16 |
Correct |
232 ms |
13916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
3408 KB |
Output is correct |
2 |
Correct |
2 ms |
3412 KB |
Output is correct |
3 |
Correct |
2 ms |
3412 KB |
Output is correct |
4 |
Correct |
2 ms |
3412 KB |
Output is correct |
5 |
Correct |
2 ms |
3412 KB |
Output is correct |
6 |
Correct |
2 ms |
3412 KB |
Output is correct |
7 |
Correct |
2 ms |
3412 KB |
Output is correct |
8 |
Correct |
2 ms |
3412 KB |
Output is correct |
9 |
Incorrect |
2 ms |
3416 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |