Submission #1204790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204790		Trn115	지도 색칠하기 (GA3_map)	C++20	Compilation error	0 ms	0 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;
		}
	};

Compilation message (stderr)

map.cpp: In function 'long long int NumberOfMaps(int, int, int*, int*)':
map.cpp:99:11: error: expected '}' at end of input
   99 |         };
      |           ^
map.cpp:45:55: note: to match this '{'
   45 | long long NumberOfMaps (int N, int M, int *A, int *B) {
      |                                                       ^
map.cpp:99:11: warning: no return statement in function returning non-void [-Wreturn-type]
   99 |         };
      |           ^