제출 #940884

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940884		NK_	Colors (RMI18_colors)	C++17	0 / 100	152 ms	8268 KiB

colors

// 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
• Subtask 2: 0 / 7
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 10
• Subtask 8: 0 / 22