oj.uz

Submission #940884

# Submission time Handle Problem Language Result Execution time Memory
940884 2024-03-07T22:36:55 Z NK_ Colors (RMI18_colors) C++17
0 / 100
 152 ms 8268 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())

template<class T> using V = vector<T>;
using vi = V<int>;

const int nax = 1e5+5;

int e[nax];
set<int> have[nax];

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

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) return 0;
	if (e[x] > e[y]) swap(x, y);
	e[x] += e[y]; 
	if (sz(have[x]) < sz(have[y])) have[x].swap(have[y]);
	for(auto& c : have[y]) have[x].insert(c);
	e[y] = x; return 1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int T; cin >> T; while(T--) {
		int N, M; cin >> N >> M;
		reset(N);

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

		V<vi> adj(N); for(int i = 0; i < M; i++) {
			int u, v; cin >> u >> v; --u, --v;
			adj[u].pb(v);
			adj[v].pb(u);
		}

		vi ord(N); iota(begin(ord), end(ord), 0);
		sort(begin(ord), end(ord), [&](int x, int y) {
			return B[x] < B[y];
		});
		
		bool pos = 1;
		for(int l = 0; l < N; l++) {
			int r = l; vi add; 
			while(r < N && B[ord[l]] == B[ord[r]]) {
				add.pb(ord[r++]);
			}


			// cout << l << " <-> " << r << endl;
			for(auto& u : add) {
				// cout << "CON: " << u << endl;
				have[get(u)].insert(A[u]);

				for(auto& v : adj[u]) if (B[v] <= B[u]) unite(v, u);	
			}

			for(auto& u : add) {
				// cout << "CHK: " << u << " => " << B[u] << endl;

				pos &= have[get(u)].count(B[u]);
			}
			l = r - 1;
		}

		cout << pos << nl;
	}

	exit(0-0);
}

Subtask #1
0 / 15.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 8.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 7.0

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

Subtask #6
0 / 16.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 22.0

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