Submission #936009

#	Time	Username	Problem	Language	Result	Execution time	Memory
936009		MinaRagy06	Joker (BOI20_joker)	C++17	14 / 100	2047 ms	6776 KiB

Joker

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 200'005;
int par[N], sz[N], dep[N];
bool gud;
array<int, 2> find(int u) {
	if (par[u] == u) {
		return {u, 0};
	}
	array<int, 2> v = find(par[u]);
	v[1] ^= dep[u];
	return v;
}
void join(int u, int v) {
	array<int, 2> pu = find(u), pv = find(v);
	if (pu[0] == pv[0]) {
		gud &= dep[pv[0]] == (pv[1] ^ pu[1] ^ 1);
		return;
	}
	if (sz[pu[0]] < sz[pv[0]]) {
		swap(u, v);
		swap(pu, pv);
	}
	par[pv[0]] = pu[0];
	dep[pv[0]] = (pv[1] ^ pu[1] ^ 1);
	sz[pu[0]] += sz[pv[0]];
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int n, m, q;
	cin >> n >> m >> q;
	array<int, 2> e[m];
	for (int i = 0; i < m; i++) {
		cin >> e[i][0] >> e[i][1];
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		l--, r--;
		for (int i = 1; i <= n; i++) {
			par[i] = i;
			sz[i] = 1;
			dep[i] = 0;
		}
		gud = 1;
		for (int i = 0; i < l; i++) {
			join(e[i][0], e[i][1]);
		}
		for (int i = r + 1; i < m; i++) {
			join(e[i][0], e[i][1]);
		}
		if (gud) {
			cout << "NO\n";
		} else {
			cout << "YES\n";
		}
	}
	return 0;
}

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