oj.uz

Submission #942010

# Submission time Handle Problem Language Result Execution time Memory
942010 2024-03-10T02:12:18 Z NK_ Colors (RMI18_colors) C++17
22 / 100
 143 ms 864 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 : e[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 63 ms 344 KB Output is correct
2 Correct 20 ms 348 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 46 ms 864 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 344 KB Output is correct
2 Correct 20 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Incorrect 63 ms 512 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 143 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 604 KB Output is correct
2 Correct 9 ms 860 KB Output is correct
3 Incorrect 4 ms 604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 344 KB Output is correct
2 Correct 20 ms 348 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 46 ms 864 KB Output is correct
5 Incorrect 63 ms 512 KB Output isn't correct
6 Halted 0 ms 0 KB -