Submission #386657

#	Time	Username	Problem	Language	Result	Execution time	Memory
386657		maximath_1	Paths (BOI18_paths)	C++11	100 / 100	585 ms	116076 KiB

paths

#include <iostream>
#include <string>
#include <math.h>
#include <algorithm>
#include <vector>
#include <string.h>
#include <numeric>
#include <iostream>
#include <queue>
#include <assert.h>
#include <map>
#include <set>
#include <limits.h>
#include <random>
#include <chrono>
using namespace std;
 
#define ll long long
#define ld long double
const int MX = 300005;
const int BLOCK = 105;
const ll inf = 8000000000000000069ll;
const ll mod = 1e9 + 7;
const ll inv2 = (mod + 1) / 2;
const int dxh[] = {1, 1, -1, -1, 2, 2, -2, -2};
const int dyh[] = {2, -2, 2, -2, 1, -1, 1, -1}; // horse
const int dx[] = {1, -1, 0, 0, 0, 0};
const int dy[] = {0, 0, 1, -1, 0, 0}; // adj
const int dz[] = {0, 0, 0, 0, 1, -1};
const int dxd[] = {1, 1, 1, 0, -1, -1, -1, 0};
const int dyd[] = {1, 0, -1, -1, -1, 0, 1, 1}; // diag

int n, m, k, col[MX];
vector<int> adj[MX];
ll dp[MX][40];

int main(){
	cin.tie(0) -> sync_with_stdio(0);

	cin >> n >> m >> k;
	for(int i = 1; i <= n; i ++) cin >> col[i];
	for(int u, v, i = 0; i < m; i ++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	ll ans = 0ll;

	for(int msk = 1; msk < (1 << k); msk ++){
		for(int i = 1; i <= n; i ++){
			dp[i][msk] = 0;
			if((msk & (1 << (col[i] - 1))) == 0) continue;
			if(msk - (1 << (col[i] - 1)) == 0) dp[i][msk] = 1;
			for(int nx : adj[i])
				dp[i][msk] += dp[nx][msk - (1 << (col[i] - 1))];

			ans += dp[i][msk];
		}
	}

	ans -= n;

	cout << ans << endl;
	return 0;
}

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