Submission #1304933

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304933		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);
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]) {
		if(Find(u) != Find(v)) continue;
		change_dfs(u);
	}
}

bool polacz(int i) {
	auto[a,b] = edges[i];
	saved.push_back({});
	saved_ans.push_back(ans);
	if(color[a]==color[b]) {
		saved.back().push_back({0,0});
		saved.back().push_back({0,0});
	} else {
		if(Find(a)!=Find(b)) {
			int a = Find(a);
			int 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]});
			change_dfs(b);
			while(to_del.size()) {
				vis[to_del.back()] = 0;
				to_del.pop_back();
			}
			rep[b] = a;
			sajz[a] += sajz[b];
		} else {
			saved.back().push_back({0,0});
			saved.back().push_back({0,0});
			ans = 0;
			return 0;
		}
	}
	return 1;
}

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;
	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;
		g[a].push_back(b);
		g[b].push_back(a);
		edges.push_back({a,b});
	}
	// for(int i=0; i<n; ++i) cout << lim[i] << " "; cout << '\n';
	lim[0] = m;
	while(lim[0] > 0 && ans) {
		polacz(lim[0]-1);
		lim[0]--;
	}
	lim[0]++;
	while(q--) {
		int l, r;
		cin >> l >> r;
		--l; --r;
		if(r < lim[l]) 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