Submission #257444

#	Time	Username	Problem	Language	Result	Execution time	Memory
257444		easrui	Joker (BOI20_joker)	C++14	100 / 100	609 ms	16544 KiB

Joker

#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef pair<int,int> pii;

const int MN = 2e5+5;

int N,M,Q,pos;
int par[MN<<1],sz[MN<<1],ans[MN];
pii E[MN];

vector<pii> qu;
vector<int> cnt;

int fnd(int u)
{
	return u==par[u] ? u : fnd(par[u]);
}

void join(int u, int v)
{
	u = fnd(u), v = fnd(v);
	if(u==v) u = v = 0;
	if(sz[u]>sz[v]) swap(u,v);
	qu.push_back({u,v});
	par[u] = v;
	sz[v] += sz[u];

}

void upt(int x)
{
	if(x>M){
		join(0,0);
		join(0,0);
		cnt.push_back(0);
		return;
	}
	if(!x){
		for(int i=0; i<2; i++){
			pii q = qu.back();
			sz[q.vb] -= sz[q.va];
			par[q.va] = q.va;
			qu.pop_back();
		}
		pos -= cnt.back();
		cnt.pop_back();
	}
	else{
		join(E[x].va,E[x].vb+N);
		join(E[x].va+N,E[x].vb);
		if(fnd(E[x].va)==fnd(E[x].va+N)){
			pos++;
			cnt.push_back(1);
		}
		else cnt.push_back(0);
	}
}

void solve(int s, int e, int x, int y)
{
	if(s>e) return;
	int m = (s+e)/2;
	int z = y;
	for(int i=s; i<m; i++) upt(i);
	while(1){
		upt(z);
		if(pos||z==m){
			ans[m] = z;
			break;
		}
		z--;
	}
	for(int i=z; i<=y; i++) upt(0);
	for(int i=s; i<m; i++) upt(0);

	for(int i=z+1; i<=y; i++) upt(i);	
	solve(s,m-1,x,z);
	for(int i=z+1; i<=y; i++) upt(0);	

	for(int i=s; i<=m; i++) upt(i);
	solve(m+1,e,max(m+1,z),y);
	for(int i=s; i<=m; i++) upt(0);
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N >> M >> Q;

    for(int i=1; i<=M; i++) cin >> E[i].va >> E[i].vb;

    for(int i=1; i<=2*N; i++){
    	par[i] = i;
    	sz[i] = 1;
    }
    solve(1,M,1,M+1);

    while(Q--){
    	int l,r;
    	cin >> l >> r;
    	cout << (r<ans[l] ? "YES\n" : "NO\n");
    }
}

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