oj.uz

Submission #652643

# Submission time Handle Problem Language Result Execution time Memory
652643 2022-10-23T15:23:50 Z lovrot Joker (BOI20_joker) C++17
0 / 100
 78 ms 6804 KB 
#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, 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}, {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, pii> e = event.top();
		event.pop();
		int u = e.X.X;
		int v = e.X.Y;
		par[u] = u;
		par[v] = v;
		eq[u] = 0;
		eq[v] = 0;
		siz[u] = e.Y.X;
		siz[v] = e.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;
	bool flag = 0;
	for(int i = 1; i <= m; i++){
		if(flag){
			opt[i] =  m + 1;
			continue;
		}	
		bool res = change(i, true);
		if(res == 0){ 
			flag = true;
			opt[i] = m + 1;
		}
		else maxm = i;
	}	
	
	//include(1, maxm + 1, 0);	
	
	if(maxm < m){
		//divcon(1, maxm, 1, m);
	} 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

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:137:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%d%d", &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 78 ms 6804 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Incorrect 2 ms 2644 KB Output isn't correct
4 Halted 0 ms 0 KB -