oj.uz

Submission #942011

# Submission time Handle Problem Language Result Execution time Memory
942011 2024-03-10T02:13:12 Z NK_ Colors (RMI18_colors) C++17
100 / 100
 534 ms 69316 KB 
// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'
#define pb push_back
#define sz(x) int(x.size())
#define f first
#define s second
#define mp make_pair


template<class T> using V = vector<T>;
using vi = V<int>;
using pi = pair<int, int>;
using vpi = V<pi>;

const int nax = 2e5+5;
int e[nax], has[nax];
V<array<int, 4>> his;

void reset(int n) { 
	his = {};
	for(int i = 0; i < n; i++) e[i] = -1; 
}

int get(int x) { return e[x] < 0 ? x : get(e[x]); }

bool unite(int x, int y) {
	x = get(x), y = get(y); 

	if (x == y) {
		his.pb({-1, -1, -1, -1});
		return 0;
	}

	if (e[x] > e[y]) swap(x, y);
	his.pb({x, y, e[x], e[y]});

	e[x] += e[y]; e[y] = x; return 1;
}

void roll(int t) {
	for(int i = 0; i < t; i++) {
		auto [x, y, ex, ey] = his.back(); his.pop_back();
		if (x == -1) continue;
		e[x] = ex, e[y] = ey;
	}
}

void solve() {
	int N, M; cin >> N >> M;
	reset(N);

	vi A(N); for(auto& x : A) { cin >> x; --x; }
	vi B(N); for(auto& x : B) { cin >> x; --x; }

	V<vi> ocA(N), ocB(N); for(int i = 0; i < N; i++) {
		ocA[A[i]].pb(i);
		ocB[B[i]].pb(i);
	}

	int K = 1; while(K < N) K *= 2;
	V<vpi> E(2 * K);

	for(int i = 0; i < M; i++) {
		int u, v; cin >> u >> v; --u, --v;

		int l = max(B[u], B[v]), r = min(A[u], A[v]);
		for(l += K, r += K+1; l < r; l /= 2, r /= 2) {
			if (l & 1) E[l++].pb(mp(u, v));
			if (r & 1) E[--r].pb(mp(u, v));
		}
	}

	int ans = 1;

	function<void(int, int, int)> answer = [&](int x, int l, int r) {
		if (l > r) return;
		// cout << x << " => " << l << " " << r << endl;
		int amt = sz(E[x]);
		for(auto& e : E[x]) {
			// cout << e.f << " " << e.s << endl;
			unite(e.f, e.s);
		}

		if (l == r) {
			if (l < N) {
				for(auto& u : ocA[l]) has[get(u)] = 1;
				for(auto& u : ocB[l]) if (!has[get(u)]) ans = 0;
				for(auto& u : ocA[l]) has[get(u)] = 0;
			}
		} else {
			int m = (l + r) / 2;
			answer(2 * x, l, m); answer(2 * x + 1, m + 1, r);
		}

		roll(amt);
	};

	answer(1, 0, K - 1);

	cout << ans << nl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	

	int T; cin >> T; while(T--) {
		solve();
	}


	exit(0-0);
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 3 ms 856 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 612 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 348 KB Output is correct
2 Correct 25 ms 1112 KB Output is correct
3 Correct 3 ms 856 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 348 KB Output is correct
2 Correct 25 ms 1112 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 139 ms 3464 KB Output is correct
5 Correct 245 ms 24652 KB Output is correct
6 Correct 367 ms 58192 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 62 ms 348 KB Output is correct
5 Correct 25 ms 1112 KB Output is correct
6 Correct 3 ms 856 KB Output is correct
7 Correct 61 ms 2008 KB Output is correct
8 Correct 23 ms 1008 KB Output is correct
9 Correct 4 ms 860 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 524 KB Output is correct
2 Correct 268 ms 23736 KB Output is correct
3 Correct 257 ms 45060 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 604 KB Output is correct
2 Correct 9 ms 860 KB Output is correct
3 Correct 4 ms 604 KB Output is correct

Subtask #8
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 344 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 3 ms 856 KB Output is correct
4 Correct 50 ms 612 KB Output is correct
5 Correct 62 ms 348 KB Output is correct
6 Correct 25 ms 1112 KB Output is correct
7 Correct 3 ms 856 KB Output is correct
8 Correct 139 ms 3464 KB Output is correct
9 Correct 245 ms 24652 KB Output is correct
10 Correct 367 ms 58192 KB Output is correct
11 Correct 61 ms 2008 KB Output is correct
12 Correct 23 ms 1008 KB Output is correct
13 Correct 4 ms 860 KB Output is correct
14 Correct 125 ms 524 KB Output is correct
15 Correct 268 ms 23736 KB Output is correct
16 Correct 257 ms 45060 KB Output is correct
17 Correct 25 ms 604 KB Output is correct
18 Correct 9 ms 860 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Correct 72 ms 3044 KB Output is correct
21 Correct 238 ms 28968 KB Output is correct
22 Correct 534 ms 69316 KB Output is correct