Submission #871044

#	Time	Username	Problem	Language	Result	Execution time	Memory
871044		NaimSS	Joker (BOI20_joker)	C++14	100 / 100	316 ms	42044 KiB

Joker

#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define pb push_back
#define ld long double
#define ff first
#define ss second
#define endl '\n'
#define sz(v) ((int)v.size())
#define all(v) begin(v),end(v)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

void dbg_out() { cerr << endl ;}
template<typename Head, typename... Tail> void dbg_out(Head H,Tail... T){
	cerr<<' '<<H ;
	dbg_out(T...);
}
#ifdef LOCAL
#define dbg(...) cerr<<"("<< #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__), cerr << endl;
#else 
#define dbg(...) 42
#endif

struct event{
	int a,b,psb,pa,corA,is_good;
	event(int a,int b,int psb,int pa,int corA,int is_good):
	a(a),b(b),psb(psb),pa(pa),corA(corA), is_good(is_good){}
};

struct DSU{
	vector<event> st;
	int is_good;
	int n;
	vi p,ps,ar;
	DSU(){}
	DSU(int n):n(n){
		p = ps = vi(n+1,1);
		ar = vi(n+1,0);
		rep(i,0,n+1)p[i] = i, ps[i] = 1, ar[i] = 0;
		is_good = 1;
	}
	int f(int x){
		while(x!=p[x])x = p[x];
		return x;
	}
	int cor(int x){
		int c=0;
		while(x!=p[x])c^=ar[x],x=p[x];
		return c;
	}
	pii F(int x){
		int c=0;
		while(x!=p[x])c^=ar[x],x=p[x];
		return pii(x,c);
	}
	bool join(int A,int B){
		auto [a,ca] = F(A);
		auto [b,cb] = F(B);
		if(ps[a] > ps[b])swap(a,b),swap(ca,cb);
		st.pb(event(a,b,ps[b],p[a],ar[a],is_good));
		if(a == b){
			if(ca == cb)is_good = 0;
			return 0;	
		}
		ps[b] += ps[a], p[a] = b;
		ar[a] = (ca^cb^1);
		// dbg(a,b,ps[a], ps[b], p[a], p[b]);
		return 1;
	}
	int can_add(int A,int B){
		auto [a,ca] = F(A);
		auto [b,cb] = F(B);
		if(a == b && ca == cb)return 0;
		return 1;
	}
	void undo(int qtd=1){
		while(qtd--){
			auto x = st.back();
			p[x.a] = x.pa,ps[x.b] = x.psb,is_good = x.is_good;
			ar[x.a] = x.corA;
			st.pop_back();
		}
	}
	void clear(){
		undo(sz(st));
	}
	int ok(){return is_good;}
	void push(pii x){
		join(x.ff,x.ss);
	}
	void pop(){ undo();}
};

const int N = 2 * (200100);
const int SQ = 400;
int a[N], b[N];
struct query{
	int l,r,id;
	query(int l,int r,int id):l(l),r(r),id(id){}
};
vector<query> Q[N];
int res[N];
#define F first
#define S second
DSU DS(N);
template<class U>
class ds_queue{
public:
	void push(U upd ){
		Q.push_back({upd, 1});
		DS.push(upd);
	}
	void pop(){
		if(!sz(Q))
			return;
		if(Q.back().S){
			vector< pair< U , bool> > block[2];
			do{
				block[Q.back().S].push_back(Q.back());
				Q.pop_back() , DS.pop();
			} while(sz(block[0]) != sz(block[1]) && sz(Q));
			if(!sz(block[0])){
				for(auto & w : block[1])
					w.S = 0 , DS.push(w.F);
				swap(Q,block[1]);
			}
			else{
				for(int j = 1; j >= 0 ; j --){
					while(sz(block[j])){
						auto w = block[j].back();
						block[j].pop_back();
						Q.push_back(w) , DS.push(w.F);
					}
				}
			}
		}
		DS.pop() , Q.pop_back();
	}
private:
	vector < pair< U , bool> > Q;
};
int first[N];

int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,qr;
	cin >> n >> m >> qr;
	for(int i=0;i<m;i++){
		cin >> a[i] >> b[i];
	}
	ds_queue<pii> q;
	vi first(2*m);
	int ptr=0;
	for(int i=0;i<2*m;i++){
		int A = a[i%m],B = b[i%m];
		while(!DS.can_add(A,B)){
			q.pop();
			ptr++;
		}
		q.push(pii(A,B));
		first[i] = ptr;
	}
	rep(i,0,qr){
		int l,r;
		cin >> l >> r;
		--l,--r;
		if(first[l  + m - 1] <= r + 1)cout << "NO\n";
		else cout<< "YES\n";
	}
	
}

Compilation message (stderr)

Joker.cpp: In member function 'bool DSU::join(int, int)':
Joker.cpp:61:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto [a,ca] = F(A);
      |        ^
Joker.cpp:62:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |   auto [b,cb] = F(B);
      |        ^
Joker.cpp: In member function 'int DSU::can_add(int, int)':
Joker.cpp:75:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   75 |   auto [a,ca] = F(A);
      |        ^
Joker.cpp:76:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |   auto [b,cb] = F(B);
      |        ^

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