oj.uz

Submission #764561

# Submission time Handle Problem Language Result Execution time Memory
764561 2023-06-23T15:10:09 Z MetalPower Joker (BOI20_joker) C++14
25 / 100
 230 ms 13484 KB 
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>
#define fi first
#define se second

const int MX = 2e5 + 10;

// Let dp[l] be the maximum index such that removing [l, dp[l]) doesn't make the graph bipartite
// Observe that dp[i] <= dp[i + 1] <= dp[i + 2]
// Hence we can do a dnc-esque solution

// also to make the complexity much lower, we can do the 2-pointer cost usually used for dp-dnc

struct dsu{
	int p[MX << 1], sz[MX << 1];
	vector<pii> operations;

	void init(){
		for(int i = 0; i < (MX << 1); i++) p[i] = i, sz[i] = 1;
	}

	int f(int x){
		if(p[x] == x) return x;
		else return f(p[x]);
	}

	int Join(int u, int v){
		int fu = f(u), fv = f(v);
		if(fu == fv) return 0;
		if(sz[fu] < sz[fv]){
			operations.push_back({p[fu], fu});
			p[fu] = fv;
			operations.push_back({sz[fv], fv});
			sz[fv] += sz[fu];
		}else{
			operations.push_back({p[fv], fv});
			p[fv] = fu;
			operations.push_back({sz[fu], fu});
			sz[fu] += sz[fv];
		}
		return 1;
	}

	void rev(int x){
		for(int i = 0; i < x; i++){
			{
				pii bk = operations.back();
				sz[bk.se] = bk.fi;
				operations.pop_back();
			}
			{
				pii bk = operations.back();
				p[bk.se] = bk.fi;
				operations.pop_back();
			}
		}
	}

	bool con(int x){
		return f(x * 2) == f(x * 2 + 1);
	}
} D;

int N, M, Q;
vector<pii> edges;
int lf = 0, rg = -1, dp[MX];

void solve(int l, int r, int optl, int optr){

	if(r < l) return;
	// cout << "solve " << l << " " << r << '\n';

	bool is_bipartite = true;
	int op = 0;
	int mid = l + r >> 1;
	for(int i = l; i < mid; i++){
		op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
		op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
		if(D.con(edges[i].fi) || D.con(edges[i].se)){
			dp[mid] = M; is_bipartite = false;
			D.rev(op); op = 0;
			break;
		} 
	}

	if(is_bipartite){

		dp[mid] = min(mid, optl);
		for(int i = optr; i >= optl && i >= mid; i--){
			op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
			op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
			if(D.con(edges[i].fi) || D.con(edges[i].se)){
				dp[mid] = i;
				D.rev(op); op = 0;
				break;
			}
		}

		for(int i = l; i <= mid; i++){
			op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
			op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
		}

		solve(mid + 1, r, dp[mid], optr);
		D.rev(op); op = 0;

	} else {

		for(int i = mid + 1; i <= r; i++) dp[i] = dp[mid];
	}

	for(int i = optr; i > dp[mid]; i--){
		op += D.Join(edges[i].fi * 2, edges[i].se * 2 + 1);
		op += D.Join(edges[i].fi * 2 + 1, edges[i].se * 2);
	}

	solve(l, mid - 1, optl, dp[mid]);
	D.rev(op); op = 0;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	cin >> N >> M >> Q;
	for(int i = 0; i < M; i++){
		int u, v; cin >> u >> v;
		edges.push_back({u, v});
	}
	edges.push_back({N + 1, N + 2});

	D.init();
	solve(0, M - 1, 0, M);

	for(int i =  0; i < Q; i++){
		int l, r; cin >> l >> r; l--, r--;
		if(r < dp[l]) cout << "YES\n";
		else cout << "NO\n";
	}
}

Compilation message

Joker.cpp: In function 'void solve(int, int, int, int)':
Joker.cpp:77:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |  int mid = l + r >> 1;
      |            ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 191 ms 9776 KB Output is correct
4 Correct 230 ms 13484 KB Output is correct
5 Correct 198 ms 13460 KB Output is correct
6 Correct 154 ms 9832 KB Output is correct
7 Correct 162 ms 9748 KB Output is correct
8 Correct 158 ms 8544 KB Output is correct
9 Correct 175 ms 9356 KB Output is correct
10 Correct 216 ms 10048 KB Output is correct
11 Correct 175 ms 9288 KB Output is correct
12 Correct 188 ms 10044 KB Output is correct
13 Correct 153 ms 8148 KB Output is correct
14 Correct 159 ms 8380 KB Output is correct
15 Correct 214 ms 9612 KB Output is correct
16 Correct 216 ms 9904 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3412 KB Output is correct
2 Correct 2 ms 3408 KB Output is correct
3 Correct 2 ms 3416 KB Output is correct
4 Correct 2 ms 3412 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Correct 2 ms 3412 KB Output is correct
7 Correct 2 ms 3412 KB Output is correct
8 Correct 2 ms 3412 KB Output is correct
9 Incorrect 2 ms 3456 KB Output isn't correct
10 Halted 0 ms 0 KB -