Submission #652662

#	Time	Username	Problem	Language	Result	Execution time	Memory
652662		lovrot	Joker (BOI20_joker)	C++17	0 / 100	70 ms	4696 KiB

Joker

#include <bits/stdc++.h> 

#define X first
#define Y second
#define pb push_back

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int N = 2 * 1e5 + 10;

int n, m, q;
int par[N], eq[N], siz[N], opt[N];
pii edge[N];

stack<pair<pii, pair<pii, pii>>> event;

pii Find(int a){
	if(par[a] == a) return {a, eq[a]};
	pii p = Find(par[a]);
	return {p.X, p.Y ^ eq[a]};
}

bool Union(int a, int b){
	pii resa = Find(a);
	pii resb = Find(b);
	a = resa.X;
	b = resb.X;
	int x = resa.Y;
	int y = resb.Y;
	
	event.push({{a, b}, {{eq[a], eq[b]}, {siz[a], siz[b]}}});
	
	if(a == b){
		return x ^ y;
	}
	
	if(siz[a] < siz[b]){
		swap(a, b);
		swap(x, y);
	}
		
	eq[b] = !(x ^ y);
	par[b] = a;
	siz[a] = siz[a] + siz[b];
	return true;
}

bool change(int x, bool state){
	if(state){
		return Union(edge[x].X, edge[x].Y);
	} else { 
		pair<pii, pair<pii, pii>> e = event.top();
		event.pop();
		int u = e.X.X;
		int v = e.X.Y;
		par[u] = u;
		par[v] = v;
		eq[u] = e.Y.X.X;
		eq[v] = e.Y.X.Y;
		siz[u] = e.Y.Y.X;
		siz[v] = e.Y.Y.Y;
	}
	return true;
}

void include(int l, int r, bool state){
	for(l; l <= r; l++){
		change(l, state);
	}
}

void divcon(int l, int r, int optl, int optr){
	if(l > r) return;
	int mi = (l + r) / 2;
	int optm = optr;
	
	include(l, mi - 1, true);
	while(change(optm, true)){
		optm--;
	}
	opt[mi] = optm;
	include(optm, optr, false);
	divcon(mi + 1, r, optm, optr);
	include(l, mi - 1, false);
	include(optm + 1, optr, true);
	divcon(l, mi - 1, optl, optm);
	include(optm + 1, optr, false);
}

int main(){
	for(int i = 1; i < N; i++){
		par[i] = i;
		eq[i] = 0;
		siz[i] = 1;
	}
	
	scanf("%d%d%d", &n, &m, &q);
	
	for(int i = 1; i <= m; i++){
		int a, b;
		scanf("%d%d", &a, &b);
		edge[i] = {a, b};
	}
	
	int maxm = 0;
	for(int i = 1; i <= m; i++){
		if(change(i, true)) break;
		maxm = i;
	}	
		
	include(1, maxm + 1, 0);	
	
	/*
	if(maxm < m){
		divcon(1, maxm, 1, m);
		for(int i = maxn + 1; i <= m; i++) opt[i] = m + 1;
	} else {
		for(int i = 1; i <= m; i++){
			opt[i] = -1;
		}
	} */
	
	//printf("opt %d = %d\n", 4, opt[4]);
	
	for(int i = 0; i < q; i++){
		int l, r;
		scanf("%d%d", &l, &r);
		if(r <= opt[l]) printf("YES\n");
		else printf("NO\n"); 
	} 
	return 0;
}

Compilation message (stderr)

Joker.cpp: In function 'void include(int, int, bool)':
Joker.cpp:70:6: warning: statement has no effect [-Wunused-value]
   70 |  for(l; l <= r; l++){
      |      ^
Joker.cpp: In function 'int main()':
Joker.cpp:100:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
Joker.cpp:130:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

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