Submission #1121469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121469		ThegeekKnight16	Joker (BOI20_joker)	C++17	49 / 100	2047 ms	17000 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
vector<int> pai, sub;
 
int find(int v) {return pai[v] = (pai[v] == v ? v : find(pai[v]));}
void une(int x, int y)
{
	x = find(x); y = find(y);
	if (x == y) return;
	if (sub[x] < sub[y]) swap(x, y);
	pai[y] = x; sub[x] += sub[y];
}
 
void init(int N)
{
	pai.resize(2*N); iota(pai.begin(), pai.end(), 0);
	sub.resize(2*N); fill(sub.begin(), sub.end(), 1);
}
 
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int N, M, Q;
	cin >> N >> M >> Q;
	vector<pair<int, int>> edges(M);
	for (auto &[x, y] : edges) {cin >> x >> y; --x; --y;}
 
	vector<vector<pair<int, int>>> queries(M); vector<bool> resp(Q);
	for (int q = 0; q < Q; q++)
	{
		int L, R; cin >> L >> R; --L; --R;
		queries[L].emplace_back(R, q);
	}
 
	bool worksOnPref = 0;
	for (int i = 0; i < M; i++)
	{
		if (queries[i].empty()) continue;
		if (!worksOnPref) init(N);
 
		for (int j = 0; j < i && !worksOnPref; j++) 
		{
			auto [X, Y] = edges[j];
			une(2*X, 2*Y+1);
			une(2*X+1, 2*Y);
			if (find(2*X) == find(2*X+1) || find(2*Y) == find(2*Y+1)) worksOnPref = 1;
		}
		
		if (worksOnPref)
		{
			for (auto [R, q] : queries[i])
				resp[q] = 1;
			continue;
		}
 
		int lastR = M-1;
		while (lastR > i)
		{
			auto [X, Y] = edges[lastR];
			une(2*X, 2*Y+1);
			une(2*X+1, 2*Y);
			if (find(2*X) == find(2*X+1) || find(2*Y) == find(2*Y+1)) break;
			--lastR;
		}
 
		for (auto [R, q] : queries[i])
			resp[q] = (R < lastR);
	}
 
	for (auto x : resp) cout << (x ? "YES" : "NO") << '\n';
}

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