Submission #652667

#	Time	Username	Problem	Language	Result	Execution time	Memory
652667		lovrot	Joker (BOI20_joker)	C++17	100 / 100	302 ms	15760 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 L, int R){
	if(l > r) return;
	int mi = (l + r) / 2;
	int k = R;
	
	include(L, mi - 1, true);
	while(change(k, true)){
		k--;
	}
	opt[mi] = k;
	include(k, R, false);
	divcon(mi + 1, r, mi, R);
	include(L, mi - 1, false);
	
	include(k + 1, R, true);
	divcon(l, mi - 1, L, k);
	include(k + 1, R, 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 lastc = 0;
	int ind = 0;
	for(int i = 1; i <= m; i++){
		lastc = i;
		if(!change(i, true)){ 
			ind = i;
			break;
		}
	}	
		
	//printf("breaking ind = %d\n", ind);
		
	include(1, lastc, 0);	
	
	if(ind){
		divcon(1, ind, 1, m);
		for(int i = ind + 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:101:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |  scanf("%d%d%d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
Joker.cpp:105:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
Joker.cpp:136:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

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