Submission #1204793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204793		Trn115	지도 색칠하기 (GA3_map)	C++20	85 / 120	1595 ms	328 KiB

map

#include <bits/stdc++.h>

using namespace std;


struct DSU {
	int n;
	vector<int> p, sz;
	
	DSU() = default;
	DSU(int n) : n(n), p(n + 1, 0), sz(n + 1, 0) {}
	
	void make_set(int v) {
		p[v] = v;
		sz[v] = 1;
	}
	
	void init() {
		for (int i = 1; i <= n; ++i) make_set(i);
	}
	
	int find_set(int v) {
		return v == p[v] ? v : p[v] = find_set(p[v]);
	}
	
	void union_sets(int u, int v) {
		u = find_set(u);
		v = find_set(v);
		if (u != v) {
			if (sz[u] < sz[v]) swap(u, v);
			sz[u] += sz[v];
			p[v] = u;
		}
	}
};

inline int getbit(int x, int i) {
	return (x >> i) & 1;
}

inline void invertbit(int &x, int i) {
	x ^= (1 << i);
}

long long NumberOfMaps (int N, int M, int *A, int *B) {
	vector<vector<int>> g(N + 1);
	DSU dsu(N); dsu.init();
	for (int i = 0; i < M; ++i) {
		g[min(A[i], B[i])].push_back(max(A[i], B[i]));
		dsu.union_sets(A[i], B[i]);
	}

	vector<bool> mark(N + 1);
	vector<vector<int>> ccs(N + 1);
	for (int i = 1; i <= N; ++i) {
		ccs[dsu.find_set(i)].push_back(i);
	}

	long long cur;
	// vector<int> color(N + 1, 0);
	// vector<vector<bool>> used(N + 1, vector<bool>(4, false));
	vector<int> used(N + 1, 0);
	function<void(int, int, int)> backtrack = [&](int s, int i, int sz) {
		int v = ccs[s][i];
		if (i == sz) {
			++cur;
			return;
		}
		// for (int x : g[v]) used[color[x] - 1] = true;
		int limit = i == 0 ? 1 : 4;
		for (int j = 1; j <= limit; ++j) {
			if (getbit(used[v], j - 1)) continue;

			// color[v] = j;
			
			bool ok = true;
			vector<int> pre;
			for (int x : g[v]) {
				pre.push_back(getbit(used[x], j - 1));
				if (!getbit(used[x], j - 1)) {
					invertbit(used[x], j - 1);
					if (used[x] == 0b1111) {
						ok = false;
					}
				}
			}
			if (ok) backtrack(s, i + 1, sz);
			int k = 0;
			for (int x : g[v]) {
				// used[x][j - 1] = pre[k];
				if (getbit(used[x], j - 1) != pre[k]) {
					invertbit(used[x], j - 1);
				}
				++k;
			}

			// color[v] = 0;
		}
	};

	long long res = 1;
	for (int i = 1; i <= N; ++i) {
		if (ccs[i].empty()) continue;
		cur = 0;
		backtrack(i, 0, ccs[i].size());
		res *= cur * 4;
	}
	return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 25 / 25
• Subtask 4: 30 / 30
• Subtask 5: 0 / 35