Submission #1112782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112782		kojac	Paths (BOI18_paths)	C++17	100 / 100	1075 ms	941236 KiB

paths

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define MAXN ((int)(3e5+2))


ll dp[MAXN][6][65], n, m, k, c[MAXN];
vector<ll> g[MAXN];



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


	cin >> n >> m >> k;

	for(int i = 1; i <= n; i++) cin >> c[i];

	for(int i = 0; i < m; i++){
		ll x, y;

		cin >> x >> y;

		g[x].push_back(y);
		g[y].push_back(x);
	}

	for(int i = 1; i <= n; i++){
		ll aux = (1<<c[i]);
		dp[i][1][aux] = 1;
	}

	for(int i = 2; i <= k; i++){
		for(int j = 1; j <= n; j++){
			for(int bm = 0; bm < (1<<(k+1)); bm++){
				if((bm & (1<<c[j])) == 0) continue;

				ll aux = bm-(1<<c[j]);

				for(int x = 0; x < g[j].size(); x++){
					dp[j][i][bm] += dp[g[j][x]][i-1][aux];
				}


			}
		}
	}

	ll ans = 0;

	for(int i = 2; i <= k; i++){
		for(int j = 1; j <= n; j++){
			for(int aux = 0; aux < (1<<(k+1)); aux++){
				ans += dp[j][i][aux];
			}
		}
	}

	// cout << dp[1][3][6] << " AQQ\n";

	cout << ans << endl;

	return 0;

}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int x = 0; x < g[j].size(); x++){
      |                    ~~^~~~~~~~~~~~~

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