| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1114235 |
2024-11-18T12:05:22 Z |
raczek |
Joker (BOI20_joker) |
C++17 |
|
1 ms |
336 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){
debug(x);
debug(edg[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 rollback(){
while(operWght.back() --> 0){
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 rec(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;
for(int i=l1;i<=mid;i++)
dsu.add(i);
debug(mid);
debug(dsu.isOddCyc);
int opt = r2;
int cnt = 0;
if(!dsu.isOddCyc)
for(int i=r2-1;i>=r1;i--){
cnt += dsu.add(i);
if(dsu.isOddCyc == true){
opt = i;
break;
}
}
pos[mid] = opt;
int d = r2 - opt;
while(d --> 0) cnt += dsu.rollback();
for(int i=r1;i<max(mid+1, opt);i++) cnt += dsu.add(i);
rec(mid+1, l2, max(mid+1, opt), r2);
d = max(mid+1, opt) - r1 + mid - l1 + 1;
while(d --> 0) cnt += dsu.rollback();
for(int i=min(r2, m-1);i>opt;i--) cnt += dsu.add(i);
for(int i=l2;i>=mid;i--) cnt += dsu.add(i);
rec(l1, mid-1, r1, opt);
while(cnt --> 0) dsu.rollback();
}
solve()
{
cin>>n>>m>>q;
pos.resize(m+1);
vector<pair<int, int> > e(m);
for(auto& v : e) cin>>v.first>>v.second;
dsu.init(n, e);
rec(0, m-1, 0, m);
/*for(int i=0;i<m;i++)
{
dsu.add(i);
if(dsu.isOddCyc) {pos[i] = m; continue;}
for(int j=m-1;j>i;j--){
dsu.add(j);
}
}*/
debug(pos);
while(q --> 0)
{
int l, r;
cin>>l>>r;
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 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
