| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1114274 |
2024-11-18T13:22:49 Z |
raczek |
Joker (BOI20_joker) |
C++17 |
|
1 ms |
592 KB |
#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto&o,pair<auto,auto>p){return o<<"("<<p.first<<", "<<p.second<<")";}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{";int i=0;for(auto e:x)o<<","+!i++<<e;return o<<"}";}
#define debug(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X)
#else
#define debug(...){}
#endif
#define int long long
struct DSU{
int isOddCyc = 0;
vector<int> par;
vector<int> rnk;
vector<pair<int, int> > edg;
vector<pair<int&, int> > stck;
vector<int> operWght;
int Find(int a){
return (par[a] == a) ? a : Find(par[a]);
}
void Union(int a, int b){
a = Find(a), b = Find(b);
if(a == b) return;
if(rnk[a] < rnk[b]) swap(a, b);
stck.push_back({rnk[a], rnk[a]});
stck.push_back({par[b], par[b]});
rnk[a] += rnk[b];
par[b] = a;
}
int add(int x){
x--;
int t = stck.size();
Union(edg[x].first, edg[x].second^1);
Union(edg[x].first^1, edg[x].second);
if(Find(edg[x].first) == Find(edg[x].first^1)){
stck.push_back({isOddCyc, isOddCyc});
isOddCyc = true;
}
if(Find(edg[x].second) == Find(edg[x].second^1)){
stck.push_back({isOddCyc, isOddCyc});
isOddCyc = true;
}
operWght.push_back(stck.size() - t);
return 1;
}
int rolback(){
assert(operWght.size());
while(operWght.back() --> 0){
assert(stck.size());
stck.back().first = stck.back().second;
stck.pop_back();
}
operWght.pop_back();
return -1;
}
void init(int n, vector<pair<int, int >> e){
edg = e;
for(auto& v : edg) v.first--, v.second--;
for(auto& v : edg) v.first*=2, v.second*=2;
par.resize(n*2);
rnk.resize(n*2);
for(int i=0;i<2*n;i++) par[i] = i, rnk[i] = 1;
}
};
struct solve{
vector<int> pos;
DSU dsu;
int n, m, q;
void compute(int l1, int l2, int r1, int r2){
debug(l1, l2, r1, r2);
if(l1 > l2) return;
if(r1 > r2) return;
int mid = (l1 + l2) >> 1;
int cnt = 0;
for(int i=l1;i<mid;i++)
cnt += dsu.add(i);
int opt = 0;
for(int i=r2;i>=r1;i--){
cnt += dsu.add(i);
if(dsu.isOddCyc) {opt = i; break;}
}
pos[mid] = opt;
while(cnt --> 0) dsu.rolback();
cnt = 0;
for(int i=r2;i>opt;i--) cnt += dsu.add(i);
compute(l1, mid-1, r1, opt);
while(cnt --> 0) dsu.rolback();
cnt = 0;
for(int i=l1;i<=mid;i++) cnt += dsu.add(i);
compute(mid+1, l2, opt, r2);
while(cnt --> 0) dsu.rolback();
cnt = 0;
}
solve(){
cin>>n>>m>>q;
pos.resize(m+5);
vector<pair<int, int> > e(m);
for(auto& v : e) cin>>v.first>>v.second;
dsu.init(n, e);
compute(1, m, 1, m);
debug(dsu.stck);
debug(dsu.operWght);
for(int i=1;i<m;i++)
{
dsu.add(i);
if(dsu.isOddCyc)
pos[i+1] = m+1;
}
debug(pos);
while(q --> 0)
{
int l, r;
cin>>l>>r;
if(pos[l] > r) cout<<"YES\n";
else cout<<"NO\n";
}
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve a;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
336 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
592 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
