Submission #1114274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114274		raczek	Joker (BOI20_joker)	C++17	0 / 100	1 ms	592 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){
		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;
}

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