oj.uz

Submission #942013

# Submission time Handle Problem Language Result Execution time Memory
942013 2024-03-10T02:13:56 Z NK_ Colors (RMI18_colors) C++17
100 / 100
 381 ms 65080 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 > min(r, N - 1)) 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) {
			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 54 ms 348 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 2 ms 860 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 616 KB Output is correct

Subtask #3
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 536 KB Output is correct
2 Correct 23 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 536 KB Output is correct
2 Correct 23 ms 348 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 135 ms 540 KB Output is correct
5 Correct 228 ms 18200 KB Output is correct
6 Correct 365 ms 51288 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 348 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 62 ms 536 KB Output is correct
5 Correct 23 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 60 ms 344 KB Output is correct
8 Correct 22 ms 344 KB Output is correct
9 Correct 3 ms 604 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 548 KB Output is correct
2 Correct 239 ms 17888 KB Output is correct
3 Correct 225 ms 41372 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 600 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 54 ms 348 KB Output is correct
2 Correct 20 ms 344 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 48 ms 616 KB Output is correct
5 Correct 62 ms 536 KB Output is correct
6 Correct 23 ms 348 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 135 ms 540 KB Output is correct
9 Correct 228 ms 18200 KB Output is correct
10 Correct 365 ms 51288 KB Output is correct
11 Correct 60 ms 344 KB Output is correct
12 Correct 22 ms 344 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 124 ms 548 KB Output is correct
15 Correct 239 ms 17888 KB Output is correct
16 Correct 225 ms 41372 KB Output is correct
17 Correct 23 ms 600 KB Output is correct
18 Correct 9 ms 860 KB Output is correct
19 Correct 4 ms 604 KB Output is correct
20 Correct 67 ms 604 KB Output is correct
21 Correct 231 ms 23596 KB Output is correct
22 Correct 381 ms 65080 KB Output is correct