Submission #1114244

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114244		raczek	Joker (BOI20_joker)	C++17	0 / 100	286 ms	105672 KiB

Joker

#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);
		vector<int> npos(m+1);
		for(int i=0;i<=m;i++)
		{
			if(i+1 <= m)
			npos[i+1] = pos[i]+1;
			if(i > 0)
			continue;
			if(dsu.isOddCyc) {npos[i] = m+1; continue;}
			int cnt = 0;
			for(int j=m-1;j>i;j--){
				cnt += dsu.add(j);
				if(dsu.isOddCyc) {npos[i] = j+1; break;}
			}
			while(cnt --> 0) dsu.rollback();
		}
		debug(pos);
		while(q --> 0)
		{
			int l, r;
			cin>>l>>r;
			if(npos[l-1] > 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;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 25
• Subtask 4: 0 / 10
• Subtask 5: 0 / 22
• Subtask 6: 0 / 29