Submission #728481

#	Time	Username	Problem	Language	Result	Execution time	Memory
728481		WonderfulWhale	Paths (BOI18_paths)	C++17	100 / 100	370 ms	100472 KiB

paths

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

#define int int64_t
#define pb push_back
#define st first
#define nd second
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()

int ans[300009][1<<5];
vector<int> G[300009];
int tab[300009];

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int n, m, k;
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++) {
		cin >> tab[i];
		tab[i]--;
	}
	for(int i=0;i<m;i++) {
		int a, b;
		cin >> a >> b;
		G[a].pb(b);
		G[b].pb(a);
	}
	for(int i=1;i<=n;i++) {
		ans[i][1<<tab[i]] = 1;
	}
	int res = 0;
	for(int i=1;i<(1<<k);i++) {
		if(__builtin_popcount(i)==1) continue;
		for(int j=1;j<=n;j++) {
			if((i&(1<<tab[j]))==0) continue;
			int rem = i^(1<<tab[j]);
			for(int x:G[j]) {
				ans[j][i] += ans[x][rem];
			}
			res += ans[j][i];
		}
	}
	cout << res << "\n";
}

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