제출 #1264563

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1264563		OgradL	Joker (BOI20_joker)	C++20	14 / 100	2095 ms	7356 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});
	}

	for (auto [l, r, idx] : queries){
		DSU dsu(N);
		int ans = 0;

		for (int i = 0; i < l; i++){
			auto [a, b] = edges[i];
			ans |= dsu.onion_set(a, b) & 1;
		}

		for (int i = M-1; i > r; i--){
			auto [a, b] = edges[i];
			ans |= dsu.onion_set(a, b) & 1;
		}

		answers[idx] = ans;
	}

	for (int x : answers){
		if (x)
			cout << "YES\n";
		else
			cout << "NO\n";
	}

	return 0;
}

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