Submission #1092127

#	Time	Username	Problem	Language	Result	Execution time	Memory
1092127		lovrot	Paths (BOI18_paths)	C++17	100 / 100	216 ms	97216 KiB

paths

#include <cstdio>
#include <vector>
#include <algorithm>

#define debug(...) fprintf(stderr, __VA_ARGS__)
#define PB push_back

using namespace std; 

typedef long long ll;

const int N = 3e5 + 10;
const int K = 5;

int n, m, k, c[N];
vector<int> g[N];

ll dp[N][1 << K];

int next_perm(int x, int k) {
	int ret = x + (x & -x);
	return ret + (1 << (k - __builtin_popcount(ret))) - 1;
}

char out[K];

char* bit(int x) { 
	for(int i = 0; i < k; ++i) { 
		out[i] = '0' + (bool) (x & (1 << i));
	}
	return out;
}

int main() { 
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", c + i);
		-- c[i];
		dp[i][1 << c[i]] = 1;
	}
	for(int i = 0; i < m; ++i) { 
		int u, v;
		scanf("%d%d", &u, &v);
		g[u].PB(v);
		g[v].PB(u);
	}

	ll ans = 0;
	for(int i = 2; i <= k; ++i) { 
		int mask = (1 << i) - 1;
		for(; mask < (1 << k); mask = next_perm(mask, i)) {
//			printf("%d %.*s\n", mask, k, bit(mask));
			for(int u = 1; u <= n; ++u) { 
				if(mask & (1 << c[u])) { 
					for(int v : g[u]) { 
						dp[u][mask] += dp[v][mask ^ (1 << c[u])];
					}
//					if(i == 2) { printf("%d %lld\n", u, dp[u][mask]); }
					ans += dp[u][mask];
				}
			}
		}
	}

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

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:35:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |  scanf("%d%d%d", &n, &m, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
paths.cpp:37:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |   scanf("%d", c + i);
      |   ~~~~~^~~~~~~~~~~~~
paths.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

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