Submission #871033

#	Time	Username	Problem	Language	Result	Execution time	Memory
871033		NaimSS	Joker (BOI20_joker)	C++14	14 / 100	2060 ms	26480 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(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;
	}
	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;}
};

const int N = 2 * (200100);
const int SQ = 700;
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];
int32_t main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,q;
	cin >> n >> m >> q;
	rep(i,0,m){
		cin >> a[i] >> b[i];
		a[i + m] = a[i], b[i+m] = b[i];
	}
	rep(i,1,q+1){
		int l,r;
		cin >> l >> r;
		--l,--r;
		if( l == 0 && r == m - 1){
			res[i] = 1;
			continue;
		}
		Q[(r+1)/SQ].pb(query(r+1,l+m-1,i));
	}
	DSU d(n);
	for(int bk=0;bk<(N/SQ) + 1;bk++){
		if(sz(Q[bk])==0)continue;
		d.clear();
		sort(all(Q[bk]),[&](query a,query b){
			return a.r < b.r;
		});

		int ptr = (bk + 1) * SQ;
		int lB = ptr - 1;
		for(auto q : Q[bk]){
			int l = q.l,r = q.r;
			assert(l <= r);
			while(ptr <= r){
				d.join(a[ptr], b[ptr]);
				ptr++;
			}
			int qtd=0;
			for(int i=min(r,lB);i >= l; i--){
				d.join(a[i], b[i]);
				qtd++;
			}
			res[q.id] = d.ok();
			assert(qtd <= SQ);
			d.undo(qtd);
		}
	}
	rep(i,1,q+1){
		cout << (res[i] == 1 ? "NO" : "YES") << endl; 
	}
	
}

Compilation message (stderr)

Joker.cpp: In member function 'bool DSU::join(int, int)':
Joker.cpp:60:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   60 |   auto [a,ca] = F(A);
      |        ^
Joker.cpp:61:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   auto [b,cb] = F(B);
      |        ^
Joker.cpp:25:18: warning: statement has no effect [-Wunused-value]
   25 | #define dbg(...) 42
      |                  ^~
Joker.cpp:70:3: note: in expansion of macro 'dbg'
   70 |   dbg(a,b,ps[a], ps[b], p[a], p[b]);
      |   ^~~

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