Submission #858520

#	Time	Username	Problem	Language	Result	Execution time	Memory
858520		serifefedartar	Paths (BOI18_paths)	C++17	23 / 100	3081 ms	7072 KiB

paths

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 998244353;
const ll LOGN = 18; 
const ll INF = 1e15;
const ll MAXN = 3e5 + 5;

vector<vector<int>> graph;
int t[MAXN];
ll ans = 0;
void dfs(int node, int mask_now, int target) {
	if (mask_now == target)
		ans++;

	for (auto u : graph[node]) {
		if ((1<<t[u]) & mask_now)
			continue;

		if ((1<<t[u]) & target)
			dfs(u, mask_now | (1<<t[u]), target);
	}
}

int main() {
	fast
	int N, M, K, a, b;
	cin >> N >> M >> K;

	graph = vector<vector<int>>(N+1, vector<int>());
	for (int i = 1; i <= N; i++)
		cin >> t[i], t[i]--;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}

	for (int i = 0; i < (1<<K); i++) {
		for (int node = 1; node <= N; node++) {
			if ((1<<t[node]) & i)
				dfs(node, 1<<t[node], i);
		}
	}
	cout << ans - N << "\n";
}

• Subtask 1: 23 / 23
• Subtask 2: 0 / 20
• Subtask 3: 0 / 27
• Subtask 4: 0 / 30