Submission #1056120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056120		allin27x	Joker (BOI20_joker)	C++17	100 / 100	357 ms	51756 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ll __int128
const int mod = 1e9+7;
#define forn(i,n) for(int i=0; i<n; i++)
#define readv(a,n) vector<int>a(n);forn(i,n)cin>>a[i];
#define readvv(a,n,m) vector<vector<int>> a(n,vector<int>(m));forn(i,n)forn(j,m)cin>>a[i][j];
#define all(a) a.begin(), a.end()
#define _max(x,y) x = max(x,y)
#define _min(x,y) x = min(x,y)
// #define f first
// #define s second

struct DSU{
	vector<int> par;
	vector<int> size;
	stack<int> rb;
	stack<char> tp;
	stack<int> bad;
	stack<pair<int,int>> edg;
	int nb;  int A = 0; int k;
	DSU(int n){
		k = n/2; par.resize(n); for(int i=0; i<n; ++i) par[i]=i;
		size.resize(n,1); nb = 0;
	}
	int get(int p){
		return par[p]==p? p: get(par[p]);
	}
	void unite(int a, int b){
		edg.push({a,b});
		if (get(a%k) == get(b%k)) {
			nb++; bad.push(1);
		} else bad.push(0);
		a = get(a); b = get(b);
		if (a==b){
			rb.push(-1);
			return;
		}
		if (size[a] > size[b]) swap(a,b);
		rb.push(a);
		size[b]+=size[a];
		par[a] = b;
	}
	void rollbackHelper(){
		int f = rb.top();
		rb.pop();
		nb -= bad.top(); bad.pop();
		edg.pop();
		if (f==-1) return;
		size[par[f]] -= size[f];
		par[f] = f;
	}
	void change(){
		stack<pair<int,int>> edA,edB;
		edB.push({edg.top().first, edg.top().second}); rollbackHelper();
		int a=0, b=1; tp.pop();
		while (A!=a && a!=b){
			if (tp.top()=='A'){
				a++; edA.push({edg.top().first, edg.top().second}); 
			} else {
				b++; edB.push({edg.top().first, edg.top().second}); 
			}
			tp.pop(); rollbackHelper();
		}
		while (!edB.empty()){
			unite(edB.top().first, edB.top().second);
			edB.pop();
			tp.push('B');
		}
		while (!edA.empty()){
			unite(edA.top().first, edA.top().second);
			edA.pop();
			tp.push('A'); 
		}
	}

	void rollback(){
		if (tp.top() == 'B') change();
		int f = rb.top();
		rb.pop();
		nb -= bad.top(); bad.pop();
		A--; tp.pop(); edg.pop();
		if (f==-1) return;
		size[par[f]] -= size[f];
		par[f] = f;
	}
};


const int N = 2e5+4;
int ans[N];
int edg[N][2];
int bad[N];

void solve(){
	int n,m,q; cin>>n>>m>>q;
	for (int i=0; i<m; i++){
		int a,b; cin>>a>>b; a--; b--; 
		edg[i][0] = a; edg[i][1] = b;
	}
	DSU dsu(2*n);
	for (int i=0; i<m; i++){
		dsu.tp.push('A'); dsu.tp.push('A'); dsu.A+=2;
		dsu.unite(edg[i][0], edg[i][1]+n);
		dsu.unite(edg[i][0]+n, edg[i][1]);
	}
	int l=m; 
	for (int r = m-1; r>=0; r--){
		while (l>0 && dsu.nb){
			l--;
			// cout<<l<<' '<<dsu.nb<<'\n';
			dsu.rollback(); dsu.rollback();
		}
		ans[r]  = l+1;
		// cout<<l<<' '<<r<<' '<<ans[r]<<'\n';
		if (l==r+1) {dsu.rollback(); dsu.rollback(); l--;}
		dsu.unite(edg[r][0], edg[r][1] + n);
		dsu.unite(edg[r][0] + n, edg[r][1]);
		dsu.tp.push('B'); dsu.tp.push('B');
	}
	DSU d(2*n);
	for (int i=m-1; i>=0; i--){
		d.unite(edg[i][0], edg[i][1]+n);
		d.unite(edg[i][0]+n, edg[i][1]);
		if (d.nb) bad[i] = 1;
	}
	while (q--){
		int l, r; cin>>l>>r; l--; r--;
		l = min(l, r+1);
		cout<<(bad[r+1]||ans[r]<=l? "YES\n":"NO\n");
	}
}


signed main(){ 
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int t = 1;
	while(t--){
		solve();
	}	
	return 0;
}

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