Submission #670009

#	Time	Username	Problem	Language	Result	Execution time	Memory
670009		radal	Joker (BOI20_joker)	C++17	100 / 100	434 ms	11732 KiB

Joker

#include <bits/stdc++.h>
#pragma GCC target("sse,sse2,avx2")
#pragma GCC optimize("unroll-loops,O2")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
constexpr int N = 2e5+10,mod = 1e9+7,maxm = 210;
constexpr ll inf = 1e9+10;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
   // if (a+b < 0) return a+b+mod;
    return a+b;
}

inline int poww(int a,int k){
    if (k < 0) return 0;
    int z = 1;
    while (k){
        if (k&1) z = 1ll*z*a%mod;
        a = 1ll*a*a%mod;
        k >>= 1;
    } 
    return z; 
}

int n,m,q;
int par[N],h[N],sz[N];
int opt[N];
vector<pll> ed;
pll pa;
stack<int> st;

int getpar(int v){
	if (v == par[v]) return v;
	return getpar(par[v]);
}

bool geth(int v){
	if (v == par[v]) return 0;
	return geth(par[v])^h[v]; 
}

bool mg(int u,int v){
	int p1 = getpar(u);
	int p2 = getpar(v);
	if (p1 == p2){
		if (geth(v) == geth(u)) return 0;
		st.push(-1);
		return 1;
	}
	if (sz[p1] > sz[p2]) swap(p1,p2);
	st.push(p1);
	h[p1] = geth(u)^geth(v)^1;
	par[p1] = p2;
	sz[p2] += sz[p1];
	return 1;
}

void undo(){
	int v = st.top();
	int p = par[v];
	sz[p] -= sz[v];
	par[v] = v;
	h[v] = 0;
	st.pop();
}

void solve(int l,int r,int s,int e){
	if (r == l) return;
	int siz = st.size();
	int mid = (l+r) >> 1;
	pll tmp = pa;
	while (pa.Y-1 > mid){
		pa.Y--;
		mg(ed[pa.Y].X,ed[pa.Y].Y);
	}
	while (pa.X < s){
		mg(ed[pa.X].X,ed[pa.X].Y);
		pa.X++;
	}
	int R = min(e,mid+1);
	rep(i,s,R){
		if (!mg(ed[i].X,ed[i].Y)){
			opt[mid] = i;
			break;
		}
	}
	while ((int) st.size() > siz) undo();
	pa = tmp;
	if (r-l == 1) return;
    while (pa.X < s){
        mg(ed[pa.X].X,ed[pa.X].Y);
        pa.X++;
    }
    while (pa.Y > r){
        pa.Y--;
        mg(ed[pa.Y].X,ed[pa.Y].Y);
    }
	solve(l,mid,s,opt[mid]+1);
	solve(mid+1,r,opt[mid],e);
	while ((int) st.size() > siz) undo();
	pa = tmp;
}

int main(){
	ios :: sync_with_stdio(0);	cin.tie(0);
	cin >> n >> m >> q;
	rep(i,1,n+1){
	   	par[i] = i;
		sz[i] = 1;
	}
	rep(i,0,m){
		int u,v;
		cin >> u >> v;
		ed.pb({u,v});
	}

	int L = -1;
	repr(i,m-1,0){
		int u = ed[i].X,v = ed[i].Y;
		int p1 = getpar(u),p2 = getpar(v);
		if (p1 != p2){
			if (sz[p1] > sz[p2]) swap(p1,p2);
			h[p1] = geth(u)^geth(v)^1;
			par[p1] = p2;
			sz[p2] += sz[p1];
			continue;
		}
		else if (geth(u) == geth(v)){
		   	L = i;
			break;
		}
	}
	if (L == -1){
		while (q--) cout << "NO" << endl;
		return 0;
	}
	rep(i,0,L) opt[i] = -inf;
	pa = {0,m};
	rep(i,1,n+1){
		par[i] = i;
		h[i] = 0;
		sz[i] = 1;
	}
	solve(L,m,0,m);
	//rep(i,0,m) debug(opt[i]);
	while (q--){
		int l,r;
		cin >> l >> r;
		l--;
		if (opt[r-1] < l) cout << "YES" << endl;
		else cout << "NO" << endl;
	}
}

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