Submission #1303682

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303682		BuiDucManh123	Joker (BOI20_joker)	C++20	71 / 100	2017 ms	11024 KiB

Joker

#include<bits/allocator.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O1")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,mmx,abm")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define ldb long double
#define pii pair<int, int>
#define bend(v) v.begin(), v.end()
const int N = 4e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const int S = 595, NB = (N + S - 1) / S;

int n, m, q;
pii ed[N], qu[N];
struct query{
	int l, r, id;
};
vector<query> block[NB + 5];

struct upd{
	int u, v;
	bool cu, cv;
	int su;
	bool state;
};

vector<upd> st;
struct dsu{
	int par[N], si[N];
	bool col[N], state;

	inline void build(){
		state = 1;
		for(int i = 1; i <= n; i++){
			par[i] = i; si[i] = 1;
			col[i] = 0;
		}
	}

	inline pii fpar(int u){
		int c = col[u];
		while(u != par[u]){
			u = par[u];
			c ^= col[u];
		}
		return {u, c};
	}
	
	inline void uni(int u, int v, bool roll){
		pii x1 = fpar(u), x2 = fpar(v);
		if(x1.fi == x2.fi){
			if(x1.se == x2.se){
				if(roll) st.push_back({0, 0, 0, 0, 0, state});
				state = 0;
			}
			return;
		}
		if(si[x1.fi] < si[x2.fi]) swap(x1, x2);
		if(roll){
			int p = x1.fi, q = x2.fi;
			st.push_back({p, q, col[p], col[q], si[p], state});
		}
		if(x1.se == x2.se){
			col[x2.fi] ^= 1;
		}
		si[x1.fi] += si[x2.fi];
		par[x2.fi] = x1.fi;
	}

	inline void rollback(){
		while(!st.empty()){
			upd x = st.back(); st.pop_back();
			par[x.v] = x.v;
			si[x.u] = x.su;
			col[x.v] = x.cv;
			state = x.state;
		}
	}
} f;

inline bool comp(query x, query y){
	return x.r < y.r;
}

bool ans[N];

void solve(){
	
	cin>>n>>m>>q;
	for(int i = 1; i <= m; i++) cin>>ed[i].fi>>ed[i].se;
	for(int i = m + 1; i <= 2 * m; i++) ed[i] = ed[i - m];
	for(int i = 1; i <= q; i++){
		int l, r; cin>>l>>r;
		qu[i] = {r + 1, l - 1 + m};
		block[qu[i].fi / S].push_back({qu[i].fi, qu[i].se, i});
	}
	for(int idk = 0; idk < NB; idk++){
		if(block[idk].empty()) continue;
		sort(bend(block[idk]), comp);
		int pre = min(m + 1, S * (idk + 1)), start = pre;
		f.build();
		for(query cur : block[idk]){
			int l = cur.l, r = cur.r, id = cur.id;
			if(l > r){
				ans[id] = 1;
				continue;
			}
			if(r >= pre){
				for(int i = pre; i <= r; i++){
					f.uni(ed[i].fi, ed[i].se, 0);
				}
				pre = r + 1;
			}
			for(int i = start - 1; i >= l; i--){
				f.uni(ed[i].fi, ed[i].se, 1);
			}
			ans[id] = f.state;
			f.rollback();
		}
	}
	for(int i = 1; i <= q; i++) cout<<(!ans[i] ? "YES\n" : "NO\n");
}

signed main(){
	
	// freopen(".inp", "r", stdin);
	// freopen(".out", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int tc = 1;
	// cin>>tc;
	while(tc--) solve();
}

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