제출 #1204773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1204773		Trn115	지도 색칠하기 (GA3_map)	C++20	85 / 120	1596 ms	416 KiB

map

#pragma GCC optimize("O3,unroll-loops")
#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;
		}
	}
};

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[max(A[i], B[i])].push_back(min(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);
	function<void(int, int, int)> backtrack = [&](int s, int i, int sz) {
		if (i == sz) {
			++cur;
			return;
		}
		array<bool, 4> used = {false, false, false, false};
		for (int x : g[ccs[s][i]]) used[color[x] - 1] = true;
		for (int j = 1; j <= 4; ++j) {
			if (used[j - 1]) continue;
			
			color[ccs[s][i]] = j;
			backtrack(s, i + 1, sz);
		}
	};

	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;
	}
	return res;

}

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