oj.uz

답안 #877228

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
877228 2023-11-23T04:07:50 Z TranGiaHuy1508 Joker (BOI20_joker) C++17
0 / 100
 150 ms 40048 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

using ii = pair<int, int>;

struct DSU_Rollback_Bipartite{
	using Change = pair<int*, int>;
	using Changes = vector<Change>;

	vector<int> parent, size;
	vector<Changes> changes;
	int is_bipartite;

	DSU_Rollback_Bipartite() {}
	DSU_Rollback_Bipartite(int N): parent(N), size(N, 1) {
		iota(parent.begin(), parent.end(), 0);
		is_bipartite = 1;
	}

	int get(int x){
		return (x == parent[x]) ? x : get(parent[x]);
	}

	void merge(int a, int b){
		changes.emplace_back();
		a = get(a); b = get(b);

		if (a == b){
			changes.back().emplace_back(&is_bipartite, is_bipartite);
			is_bipartite = 0;
			return;
		}

		if (size[a] < size[b]) swap(a, b);

		changes.back().emplace_back(&parent[b], parent[b]);
		changes.back().emplace_back(&size[a], size[a]);

		parent[b] = a;
		size[a] += size[b];
	}

	void rollback(){
		for (auto [pointer, value]: changes.back()){
			*pointer = value;
		}
		changes.pop_back();
	}
};

struct DSU_Queue_Rollback{
	using Query = pair<ii, int>;
	vector<Query> st;
	DSU_Rollback_Bipartite ds;
	int bottom;

	DSU_Queue_Rollback() {}
	DSU_Queue_Rollback(int N): ds(N), bottom(0) {}

	void merge(int a, int b){
		ds.merge(a, b);
		st.push_back({{a, b}, 0});
	}

	int is_bipartite(){
		return ds.is_bipartite;
	}

	void advance_bottom(){
		while (bottom < (int)st.size() && st[bottom].second == 0) bottom++;
	}

	void flip_all(){
		for (int i = 0; i < (int)st.size(); i++) ds.rollback();
		reverse(st.begin(), st.end());
		for (int i = 0; i < (int)st.size(); i++){
			ds.merge(st[i].first.first, st[i].first.second);
			st[i].second = 1;
		}
		bottom = 0;
	}

	void fix(){
		if (st.empty() || st.back().second == 1) return;
		vector<Query> qA, qB;

		advance_bottom();
		while ((qA.empty() && qB.empty()) ||
				(qA.size() != qB.size() && (int)st.size() >= bottom)){
			if (st.back().second == 1) qA.push_back(st.back());
			else qB.push_back(st.back());

			ds.rollback();
			st.pop_back();
		}

		reverse(qA.begin(), qA.end());
		reverse(qB.begin(), qB.end());

		for (auto query: qB){
			ds.merge(query.first.first, query.first.second);
			st.push_back(query);
		}
		for (auto query: qA){
			ds.merge(query.first.first, query.first.second);
			st.push_back(query);
		}
		
		advance_bottom();
	}

	void queue_rollback(){
		advance_bottom();
		if (bottom == (int)st.size()) flip_all();
		fix();

		ds.rollback();
		st.pop_back();
	}
};

int n, m, q;
vector<ii> edges;
DSU_Queue_Rollback dsu;

vector<int> best;

void main_program(){
	cin >> n >> m >> q;

	edges.resize(m);

	for (int i = 0; i < m; i++){
		int x, y; cin >> x >> y;
		x--; y--;
		edges[i] = {x, y};
	}

	best.resize(m);

	dsu = DSU_Queue_Rollback(n);
	for (int i = m-1; i >= 0; i--){
		dsu.merge(edges[i].first, edges[i].second);
	}

	int crr = m;
	for (int i = m-1; i >= 0; i--){
		while (!dsu.is_bipartite()){
			if (crr < 0) break;
			dsu.queue_rollback();
			crr--;
		}
		best[i] = crr;
		dsu.merge(edges[i].first, edges[i].second);
	}

	for (int _ = 0; _ < q; _++){
		int x, y; cin >> x >> y;
		x--; y--;

		if (x <= best[y]) cout << "NO\n";
		else cout << "YES\n";
	}
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 150 ms 40048 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 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 Runtime error 1 ms 348 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -