oj.uz

Submission #877255

# Submission time Handle Problem Language Result Execution time Memory
877255 2023-11-23T05:01:07 Z TranGiaHuy1508 Joker (BOI20_joker) C++17
0 / 100
 291 ms 128128 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 (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];

		int other = (a >= (int)parent.size() / 2) ? (a - parent.size() / 2)
		: (a + parent.size() / 2);
		if (get(a) == get(other)){
			changes.back().emplace_back(&is_bipartite, is_bipartite);
			is_bipartite = 0;
		}
	}

	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, _n;

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

	void merge(int a, int b){
		ds.merge(a, b + _n);
		ds.merge(a + _n, 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 + _n);
			ds.merge(st[i].first.first + _n, 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 + _n);
			ds.merge(query.first.first + _n, query.first.second);
			st.push_back(query);
		}
		for (auto query: qA){
			ds.merge(query.first.first, query.first.second + _n);
			ds.merge(query.first.first + _n, 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 + 1;
	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

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 291 ms 128128 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 456 KB Output is correct
3 Runtime error 1 ms 604 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -