Submission #473405

#	Time	Username	Problem	Language	Result	Execution time	Memory
473405		Hamed5001	Paths (BOI18_paths)	C++14	100 / 100	473 ms	95944 KiB

paths

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int mxN = 3e5+10;
/*
9 11 4 
1 2 3 4 1 2 1 2 2 
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8
*/

ll dp[mxN][1<<5];
int color[mxN];
vector<int> adj[mxN];

int N, M, K;

ll dfs(int node, int msk) {
	if (~dp[node][msk]) return dp[node][msk];

	dp[node][msk] = 1;
	int nmsk = msk | (1 << (color[node]-1));

	for (auto c : adj[node]) {
		if ((1<<(color[c]-1)) & nmsk) continue; 
		
		dp[node][msk] += dfs(c, nmsk);
	}

	return dp[node][msk];
}

void solve() {
	memset(dp, -1, sizeof dp);
	cin >> N >> M >> K;

	for (int i = 1; i <= N; i++) 
		cin >> color[i];

	for (int i = 0; i < M; i++) {
		int u, v;
		cin >> u >>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}	

	ll ans = 0;
	for (int i = 1; i <= N; i++)
		ans += dfs(i, 0);

	cout << ans - N;
}

int main() {

	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	solve();
}

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