oj.uz

Submission #810441

# Submission time Handle Problem Language Result Execution time Memory
810441 2023-08-06T09:48:41 Z ymm Joker (BOI20_joker) C++17
25 / 100
 195 ms 12372 KB 
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;

const int N = 200'010;

namespace dsu {
	int par[N];
	int sz[N];
	bool parpar[N];

	void init() { fill(par, par+N, -1); fill(sz, sz+N, 1); }
	pii rt(int v) {
		int p = 0;
		while (par[v] != -1) {
			p ^= parpar[v];
			v = par[v];
		}
		return {v, p};
	}
	bool can(int v, int u) {
		auto [x1, y1] = rt(v);
		auto [x2, y2] = rt(u);
		return x1 != x2 || y1 != y2;
	}
	vector<pii> his;
	bool unite(int v, int u) {
		auto [x1, y1] = rt(v);
		auto [x2, y2] = rt(u);
		if (x1 == x2) {
			if (y1 == y2)
				return 0;
			his.push_back({-1, -1});
			return 1;
		}
		if (sz[x1] < sz[x2]) {
			swap(x1, x2);
			swap(y1, y2);
		}
		par[x2] = x1;
		parpar[x2] = 1 ^ y1 ^ y2;
		sz[x1] += sz[x2];
		his.emplace_back(x1, x2);
		return 1;
	}
	void undo() {
		auto [x1, x2] = his.back();
		his.pop_back();
		if (x2 == -1)
			return;
		sz[x1] -= sz[x2];
		par[x2] = -1;
	}
}

pii E[N];
bool unite(int i) { return dsu::unite(E[i].first, E[i].second); }

int L, R;
vector<int> dir;

void undo() {
	dsu::undo();
	if (dir.back() == 0)
		--L;
	else
		++R;
	dir.pop_back();
}

bool mov(int l, int r)
{
	if (l > r)
		return 0;
	while (l < L)
		undo();
	while (R < r)
		undo();
	while (L < l) {
		if (!unite(L))
			return 0;
		dir.push_back(0);
		++L;
	}
	while (r < R) {
		if (!unite(R-1))
			return 0;
		dir.push_back(1);
		--R;
	}
	return 1;
}

int mn_ac[N];

void dc(int l1, int r1, int l2, int r2)
{
	if (l1 >= r1)
		return;
	//cerr << l1 << ' ' << r1 << " -> " << l2 << ' ' << r2 << '\n';
	int m = (l1 + r1)/2;
	mov(l1, r2-1);
	if (!mov(m, r2-1)) {
		Loop (i,m,r1) {
			mn_ac[i] = N;
			dc(l1, m, l2, r2);
			return;
		}
	}
	while (mov(m, R-1));
	int ans = R;
	mn_ac[m] = ans;
	//cerr << "mn[" << m << "] = " << ans << '\n';
	dc(l1, m, l1, ans+1);
	dc(m+1, r1, ans, r2);
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int n, m, q;
	cin >> n >> m >> q;
	dsu::init();
	L = 0;
	R = m;
	Loop (i,0,m) {
		int v, u;
		cin >> v >> u;
		E[i] = {v, u};
	}
	dc(0, m+1, 0, m+1);
	Loop (i,0,q) {
		int l, r;
		cin >> l >> r;
		--l;
		if (r >= mn_ac[l])
			cout << "NO\n";
		else
			cout << "YES\n";
	}
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Incorrect 1 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Incorrect 1 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 114 ms 10288 KB Output is correct
4 Correct 195 ms 11888 KB Output is correct
5 Correct 98 ms 12372 KB Output is correct
6 Correct 89 ms 10256 KB Output is correct
7 Correct 93 ms 10404 KB Output is correct
8 Correct 116 ms 9712 KB Output is correct
9 Correct 120 ms 9792 KB Output is correct
10 Correct 138 ms 10100 KB Output is correct
11 Correct 130 ms 10284 KB Output is correct
12 Correct 130 ms 10548 KB Output is correct
13 Correct 113 ms 10000 KB Output is correct
14 Correct 120 ms 10212 KB Output is correct
15 Correct 141 ms 10280 KB Output is correct
16 Correct 143 ms 10428 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Incorrect 1 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Incorrect 1 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1876 KB Output is correct
2 Correct 1 ms 1876 KB Output is correct
3 Correct 1 ms 1876 KB Output is correct
4 Incorrect 1 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -