제출 #1304943

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1304943		vlomaczk	Joker (BOI20_joker)	C++20	0 / 100	6 ms	12856 KiB

Joker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

int M = 200'010;
vector<ll> sajz(M, 1);
vector<ll> rep(M, 1);
vector<ll> color(M, -1);
vector<pair<ll, ll>> edges;
vector<ll> lim(M);
ll ans = 1;
vector<ll> saved_ans;
vector<vector<pair<ll, ll>>> saved;
vector<vector<ll>> g(M);
vector<ll> vis(M);

int Find(int v){
    return (rep[v] == v ? v : Find(rep[v]));
}

vector<ll> to_del;

void change_dfs(int v) {
	if(vis[v]) return;
	vis[v] = 1; to_del.push_back(v);
	saved.back().push_back({v, color[v]});
	color[v] = 1-color[v];
	for(auto u : g[v]) {
		change_dfs(u);
	}
}

void Union(int a, int b) {
	a = Find(a);
	b = Find(b);
	if(sajz[b] > sajz[a]) swap(a,b);
	saved.back().push_back({b, rep[b]});
	saved.back().push_back({a, sajz[a]});
	saved.back().push_back({a,b});
	change_dfs(b);
	g[a].push_back(b);
	g[b].push_back(a);
	while(to_del.size()) {
		vis[to_del.back()] = 0;
		to_del.pop_back();
	}
	rep[b] = a;
	sajz[a] += sajz[b];
}

bool polacz(int i) {
	if(!ans) return 0;
	auto[a,b] = edges[i];
	saved.push_back({});
	saved_ans.push_back(ans);
	if(color[a]==-1 && color[b]==-1) {
		color[a] = 0;
		color[b] = 0;
	} else if(color[a]==-1) color[a] = color[b];
	else if(color[b]==-1) color[b] = color[a];

	if(color[a]!=color[b]) {
		saved.back().push_back({0,0});
		saved.back().push_back({0,0});
		saved.back().push_back({0,0});
	} else {
		if(Find(a)!=Find(b)) {
			Union(a,b);
		} else {
			saved.back().push_back({0,0});
			saved.back().push_back({0,0});
			saved.back().push_back({0,0});
			ans = 0;
		}
	}
	return ans;
}

void rollback() {
	while(saved.back().size() > 2) {
		auto[a,b] = saved.back().back();
		color[a] = b;
		saved.back().pop_back();
	}
	auto[a,b] = saved.back().back(); saved.back().pop_back();
	sajz[a] = b;
	auto[c,d] = saved.back().back(); saved.back().pop_back();
	rep[c] = d;
	auto[e,f] = saved.back().back(); saved.back().pop_back();
	if(g[e].size()) g[e].pop_back();
	if(g[f].size()) g[f].pop_back();
	ans = saved_ans.back();
	saved.pop_back(); saved_ans.pop_back();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	for(int i=0; i<M; ++i) rep[i] = i;

	int n, m, q;
	cin >> n >> m >> q;
	for(int i=0; i<m; ++i) {
		int a, b;
		cin >> a >> b;
		edges.push_back({a,b});
	}
	// for(int i=0; i<n; ++i) cout << lim[i] << " "; cout << '\n';

	/*cout << polacz(4) << '\n';
	cout << polacz(3) << '\n';
	for(int i=1; i<=n; ++i) cout << color[i] << " "; cout << "\n";
	cout << polacz(2) << '\n';
	for(int i=1; i<=n; ++i) cout << color[i] << " "; cout << "\n";
	cout << polacz(1) << "\n";
	return 0;*/

	lim[0] = m;
	while(lim[0] > 0 && polacz(lim[0]-1)) {
		lim[0]--;
	}
	while(q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		if(r < lim[l]-1) cout << "TAK\n";
		else cout << "NIE\n";
	}


	return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 25
• Subtask 3: 0 / 10
• Subtask 4: 0 / 22
• Subtask 5: 0 / 29
• Subtask 6: 0 / 6