Submission #916727

#	Time	Username	Problem	Language	Result	Execution time	Memory
916727		penguin133	Paths (BOI18_paths)	C++17	100 / 100	413 ms	74368 KiB

paths

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

#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int A[300005];
vector <int> adj[300005];
vector < vector <int> > memo;
int dp(int x, int bm){
	if(memo[x][bm] != -1)return memo[x][bm];
	int ans = 1;
	for(auto i : adj[x])if(bm >> A[i] & 1)ans += dp(i, bm ^ (1 << A[i]));
	return memo[x][bm] = ans;
}

void solve(){
	int n, m, k; cin >> n >> m >> k;
	for(int i=1;i<=n;i++){
		cin >> A[i];
		A[i]--;
	}
	while(m--){
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	memo.resize(n + 1);
	for(int i = 0; i <= n; i++){
		memo[i].resize(1 << k);
		for(int j = 0; j < (1 << k); j++)memo[i][j] = -1;
	}
	int ans = 0;
	for(int i=1;i<=n;i++)ans += dp(i, ((1 << k) - 1) ^ (1 << A[i]));
	cout << ans - n << '\n';
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

paths.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~

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