oj.uz

답안 #764557

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
764557 2023-06-23T15:01:53 Z MetalPower Joker (BOI20_joker) C++14
25 / 100
 243 ms 16352 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){

		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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 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 3416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 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 3416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 190 ms 13652 KB Output is correct
4 Correct 236 ms 15948 KB Output is correct
5 Correct 195 ms 16352 KB Output is correct
6 Correct 149 ms 13632 KB Output is correct
7 Correct 153 ms 13684 KB Output is correct
8 Correct 163 ms 11824 KB Output is correct
9 Correct 178 ms 12604 KB Output is correct
10 Correct 223 ms 13460 KB Output is correct
11 Correct 180 ms 13196 KB Output is correct
12 Correct 201 ms 14160 KB Output is correct
13 Correct 166 ms 11904 KB Output is correct
14 Correct 170 ms 12308 KB Output is correct
15 Correct 243 ms 13572 KB Output is correct
16 Correct 232 ms 13916 KB Output is correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 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 3416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 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 3416 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 3408 KB Output is correct
2 Correct 2 ms 3412 KB Output is correct
3 Correct 2 ms 3412 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 3416 KB Output isn't correct
10 Halted 0 ms 0 KB -