oj.uz

답안 #911452

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
911452 2024-01-19T01:02:16 Z NK_ Joker (BOI20_joker) C++17
0 / 100
 309 ms 234900 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back

template<class T> using V = vector<T>;
using vi = V<int>;

const int INF = 1e9;
struct DSU {
	vi e, p; V<array<int, 7>> ed;void init(int N) { e = vi(N, -1); p = vi(N, 0); }
	int get(int x) { return e[x] < 0 ? x : get(e[x]); }
	int parity(int x) { return e[x] < 0 ? 0 : p[x] ^ parity(e[x]); }
	bool unite(int x, int y, int t) {
		int rx = get(x), ry = get(y);
		int px = parity(x), py = parity(y);
		// cout << x << " " << y << " " << t << endl;
		// cout << rx << " " << rx << " --> " << px << " " << py << endl;

		if (rx == ry) {
			if (px == py) return 0;
			ed.pb({-1, -1, -1, -1, -1, INF}); return 1;
		}

		if (e[rx] > e[ry]) swap(rx, ry);

		ed.pb({rx, ry, e[rx], e[ry], p[rx], p[ry], t});
		e[rx] += e[ry]; e[ry] = rx; p[ry] = px ^ py ^ 1; return 1;
	}

	bool rollback(int T) {
		if (size(ed) == 0) return 0;
		auto [rx, ry, erx, ery, prx, pry, t] = ed.back(); 

		if (t < T) return 0;
		
		ed.pop_back();
		if (rx == -1) return 1;


		e[rx] = erx, p[rx] = prx;
		e[ry] = ery, p[ry] = pry;
		return 1;
	}
};


int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, Q; cin >> N >> M >> Q;

	V<array<int, 2>> E(M); for(auto& x : E) { cin >> x[0] >> x[1]; --x[0], --x[1]; }


	vi lst(M); // lst r where when [l, r] is removed the graph is bipartite

	DSU D; D.init(N);

	int T = 0;
	int cur = 0; for(; cur < M; cur++) {
		if (!D.unite(E[cur][0], E[cur][1], T)) break;
	}

	while(D.rollback(T));

	for(int i = cur+1; i < M; i++) lst[i] = M;

	function<void(int, int, int, int)> dnc = [&](int l, int r, int lx, int rx) {
		if (l > r) return;

		int mid = (l + r) / 2;
		
		// compute lst_mid

		++T;
		for(int i = l; i < mid; i++) D.unite(E[i][0], E[i][1], T);

		// cout << "START " << endl;
		// for(auto e : D.ed) {
		// 	cout << e[0] << " <-> " << e[1] << endl;
		// }

		for(int i = rx; i >= mid; i--) {
			if (!D.unite(E[i][0], E[i][1], T)) {
				lst[mid] = i;
				break;
			}
		}


		// cout << "MID" << endl;
		// for(auto e : D.ed) {
		// 	cout << e[0] << " <-> " << e[1] << endl;
		// }

		while(D.rollback(T));
		--T;

		// cout << l << " " << mid << " " << r << " " << lst[mid] << endl;
		// cout << lx << " " << rx << endl;

		// for(auto e : D.ed) {
			// cout << e[0] << " <-> " << e[1] << endl;
		// }

		// cout << "DONE" << endl;

		// [l, mid - 1]

		++T;
		for(int i = rx; i > lst[mid]; i--) D.unite(E[i][0], E[i][1], T);
		dnc(l, mid - 1, lx, lst[mid]);

		while(D.rollback(T));
		--T;

		// [mid + 1, r]
		++T;

		for(int i = l; i <= mid; i++) D.unite(E[i][0], E[i][1], T);
		dnc(mid + 1, r, max(mid + 1, lst[mid]), rx);

		while(D.rollback(T));
		--T;
	};	

	dnc(0, cur, 0, M - 1);

	// for(int i = 0; i < M; i++) {
		// lst[i] = max(lst[i], lst[i-1]);
		// cout << i << " => " << lst[i] << nl;
	// }

	for(int i = 0; i < Q; i++) {
		int l, r; cin >> l >> r; --l, --r;
		cout << (lst[l] <= r ? "NO" : "YES") << nl;
	}

	exit(0-0);
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 273 ms 234900 KB Output is correct
4 Correct 309 ms 234572 KB Output is correct
5 Incorrect 150 ms 122672 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 604 KB Output isn't correct
9 Halted 0 ms 0 KB -