| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 652660 |
2022-10-23T16:20:38 Z |
lovrot |
Joker (BOI20_joker) |
C++17 |
|
4 ms |
5204 KB |
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 2 * 1e5 + 10;
int n, m, q;
int par[N], eq[N], siz[N], opt[N];
pii edge[N];
stack<pair<pii, pair<pii, pii>>> event;
pii Find(int a){
if(par[a] == a) return {a, eq[a]};
pii p = Find(par[a]);
return {p.X, p.Y ^ eq[a]};
}
bool Union(int a, int b){
pii resa = Find(a);
pii resb = Find(b);
a = resa.X;
b = resb.X;
int x = resa.Y;
int y = resb.Y;
event.push({{a, b}, {{eq[a], eq[b]}, {siz[a], siz[b]}}});
if(a == b){
return x ^ y;
}
if(siz[a] < siz[b]){
swap(a, b);
swap(x, y);
}
eq[b] = !(x ^ y);
par[b] = a;
siz[a] = siz[a] + siz[b];
return true;
}
bool change(int x, bool state){
if(state){
return Union(edge[x].X, edge[x].Y);
} else {
assert(event.empty());
pair<pii, pair<pii, pii>> e = event.top();
event.pop();
int u = e.X.X;
int v = e.X.Y;
par[u] = u;
par[v] = v;
eq[u] = e.Y.X.X;
eq[v] = e.Y.X.Y;
siz[u] = e.Y.Y.X;
siz[v] = e.Y.Y.Y;
}
return true;
}
void include(int l, int r, bool state){
for(l; l <= r; l++){
change(l, state);
}
}
void divcon(int l, int r, int optl, int optr){
if(l > r) return;
int mi = (l + r) / 2;
int optm = optr;
include(l, mi - 1, true);
while(change(optm, true)){
optm--;
}
opt[mi] = optm;
include(optm, optr, false);
divcon(mi + 1, r, optm, optr);
include(l, mi - 1, false);
include(optm + 1, optr, true);
divcon(l, mi - 1, optl, optm);
include(optm + 1, optr, false);
}
int main(){
for(int i = 1; i < N; i++){
par[i] = i;
eq[i] = 0;
siz[i] = 1;
}
scanf("%d%d%d", &n, &m, &q);
for(int i = 1; i <= m; i++){
int a, b;
scanf("%d%d", &a, &b);
edge[i] = {a, b};
}
int maxm = 0;
for(int i = 1; i <= m; i++){
if(change(i, true)) break;
maxm = i;
}
include(1, maxm + 1, 0);
/*
if(maxm < m){
divcon(1, maxm, 1, m);
for(int i = maxn + 1; i <= m; i++) opt[i] = m + 1;
} else {
for(int i = 1; i <= m; i++){
opt[i] = -1;
}
} */
//printf("opt %d = %d\n", 4, opt[4]);
for(int i = 0; i < q; i++){
int l, r;
scanf("%d%d", &l, &r);
if(r <= opt[l]) printf("YES\n");
else printf("NO\n");
}
return 0;
}
Compilation message
Joker.cpp: In function 'void include(int, int, bool)':
Joker.cpp:72:6: warning: statement has no effect [-Wunused-value]
72 | for(l; l <= r; l++){
| ^
Joker.cpp: In function 'int main()':
Joker.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
102 | scanf("%d%d%d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:106:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~
Joker.cpp:132:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | scanf("%d%d", &l, &r);
| ~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
4 ms |
5204 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
