oj.uz

Submission #810458

# Submission time Handle Problem Language Result Execution time Memory
810458 2023-08-06T09:56:52 Z ymm Joker (BOI20_joker) C++17
25 / 100
 221 ms 8364 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, l2, 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])
		//if (mov(l, r))
			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 2 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 2 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 123 ms 6284 KB Output is correct
4 Correct 221 ms 8364 KB Output is correct
5 Correct 99 ms 8140 KB Output is correct
6 Correct 99 ms 6188 KB Output is correct
7 Correct 95 ms 6276 KB Output is correct
8 Correct 129 ms 6392 KB Output is correct
9 Correct 160 ms 6340 KB Output is correct
10 Correct 154 ms 6528 KB Output is correct
11 Correct 136 ms 6260 KB Output is correct
12 Correct 149 ms 6484 KB Output is correct
13 Correct 119 ms 6100 KB Output is correct
14 Correct 127 ms 6148 KB Output is correct
15 Correct 153 ms 6252 KB Output is correct
16 Correct 163 ms 6320 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 2 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 2 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 2 ms 1876 KB Output isn't correct
5 Halted 0 ms 0 KB -