Submission #522392

#	Time	Username	Problem	Language	Result	Execution time	Memory
522392		LucaDantas	Paths (BOI18_paths)	C++17	100 / 100	363 ms	56712 KiB

paths

#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 3e5+10, maxk = 5;

int color[maxn], k;

long long dp[1<<maxk][maxn];

bool vis[1<<maxk][maxn];

vector<int> g[maxn];

long long solve(int x, int mask) {
	if(vis[mask][x]) return dp[mask][x];

	vis[mask][x] = 1;
	dp[mask][x] = 1;

	for(int v : g[x])
		if(!(mask & color[v])) dp[mask][x] += solve(v, mask ^ color[v]);

	return dp[mask][x];
}

int main() {
	int n, m; scanf("%d %d %d", &n, &m, &k);
	for(int i = 1; i <= n; i++)
		scanf("%d", &color[i]), color[i] = 1 << (color[i]-1);

	for(int i = 0, a, b; i < m; i++)
		scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);

	long long ans = 0;

	for(int i = 1; i <= n; i++)
		ans += solve(i, color[i]) - 1;

	printf("%lld\n", ans);
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |  int n, m; scanf("%d %d %d", &n, &m, &k);
      |            ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
paths.cpp:29:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |   scanf("%d", &color[i]), color[i] = 1 << (color[i]-1);
      |   ~~~~~^~~~~~~~~~~~~~~~~
paths.cpp:32:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |   scanf("%d %d", &a, &b), g[a].push_back(b), g[b].push_back(a);
      |   ~~~~~^~~~~~~~~~~~~~~~~

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