Submission #1264498

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264498		OgradL	Joker (BOI20_joker)	C++20	0 / 100	2094 ms	8888 KiB

Joker

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>
using namespace std;

struct DSU{

	int N;
	vector<int> sz;
	vector<pair<int, int>> par;

	DSU(int n){
		N = n;
		sz.assign(N, 1);
		par.resize(N);
		for (int i = 0; i < N; i++)
			par[i] = {i, 0};
	}

	pair<int, int> get_par(int x){
		if (x == par[x].first)
			return par[x];
		pair<int, int> parent = get_par(par[x].first);
		par[x].first = parent.first;
		par[x].second += parent.second;
		return par[x];
	}

	int onion_set(int a, int b){
		auto A = get_par(a);
		auto B = get_par(b);

		if (A.first != B.first){
			if (sz[A.first] < sz[B.first])
				swap(A, B);

			sz[A.first] += sz[B.first];
			par[B.first].first = A.first;
			par[B.first].second = B.second + 1 + A.second;

			return 0;
		}
		return A.second + B.second + 1;
	}
};

int main(){

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int N, M, Q;
	cin >> N >> M >> Q;

	vector<pair<int, int>> edges;
	int a, b;
	for (int i = 0; i < M; i++){
		cin >> a >> b;
		--a, --b;

		edges.push_back({a, b});
	}

	vector<array<int, 3>> queries;
	vector<int> answers(Q);
	int l, r;
	for (int i = 0; i < Q; i++){
		cin >> l >> r;
		--l, --r;

		queries.push_back({l, r, i});
	}

	const int BLOCK_SIZE = 500;
	int N_BLOCKS = (N + BLOCK_SIZE - 1) / BLOCK_SIZE;
	
	vector<vector<pair<int, int>>> blocks(N_BLOCKS);

	for (auto [l, r, idx] : queries){
		int lb = l / BLOCK_SIZE * BLOCK_SIZE;
		blocks[l / BLOCK_SIZE].push_back({r - lb, idx});
	}

	for (int i = 0; i < N_BLOCKS; i++){
		if (blocks[i].empty())
			continue;

		sort(blocks[i].rbegin(), blocks[i].rend());

		DSU dsu(N);

		l = 0, r = M-1;
		int ans = 0;
		int idx = 0;
		
		for (int sz = M-1; sz >= 0; sz--){
			int target = i * BLOCK_SIZE;

			while (idx < blocks[i].size() && blocks[i][idx].first == sz){
				DSU dsu2 = dsu;
				int ans2 = ans;
				int query_idx = blocks[i][idx].second;

				for (int j = l; j < queries[query_idx][0]; j++){
					auto [a, b] = edges[j];
					ans2 |= dsu2.onion_set(a, b) & 1;
				}

				answers[query_idx] = ans2;
				idx++;
			}
			if (idx == blocks[i].size())
				break;

			if (l < target){
				auto [a, b] = edges[l];
				l++;
			} else {
				auto [a, b] = edges[r];
				r--;
			}
			ans |= dsu.onion_set(a, b) & 1;
		}
	}
	
	for (int x : answers){
		if (x)
			cout << "YES\n";
		else
			cout << "NO\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