답안 #877237

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
877237	2023-11-23T04:33:22 Z	TranGiaHuy1508	Joker (BOI20_joker)	C++17	0 / 100	2000 ms	71156 KB

Joker

#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;
        if (other < 0) other += parent.size();
        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), _n(N), bottom(0) {}
 
	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);
			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";
	}
}

Compilation message

Joker.cpp: In constructor 'DSU_Queue_Rollback::DSU_Queue_Rollback(int)':
Joker.cpp:63:14: warning: 'DSU_Queue_Rollback::_n' will be initialized after [-Wreorder]
   63 |  int bottom, _n;
      |              ^~
Joker.cpp:63:6: warning:   'int DSU_Queue_Rollback::bottom' [-Wreorder]
   63 |  int bottom, _n;
      |      ^~~~~~
Joker.cpp:66:2: warning:   when initialized here [-Wreorder]
   66 |  DSU_Queue_Rollback(int N): ds(N*2), _n(N), bottom(0) {}
      |  ^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	452 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #2
0 / 8.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Incorrect	452 KB	Output isn't correct
4	Halted	0 KB	-

Subtask #3
0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	198 ms	66144 KB	Output is correct
4	Correct	135 ms	71156 KB	Output is correct
5	Execution timed out	2036 ms	25792 KB	Time limit exceeded
6	Halted	0 ms	0 KB	-