Submission #716411

#	Time	Username	Problem	Language	Result	Execution time	Memory
716411		faribourz	Paths (BOI18_paths)	C++14	100 / 100	464 ms	46100 KiB

paths

// Only GOD
// Believe in yourself!
// -o Sango zadam be shishe 
// -o Comeback bezan hamishe!
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;

#define pb push_back
#define F first
#define S second
#define bit(x, y) (x >> y)&1
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define kill(x) return cout << x << '\n', void()
#define KILL(x) return cout << x << '\n', 0
#define mid ((l+r)>>1)
#define lid (id << 1)
#define rid (lid | 1)
#define int ll
const int N = 3e5+10;
const int INF = 1e9+10;
const int M = (1<<5);
int dp[M][N];// keshi friendly!
int n, m, k;
int color[N];
vector<int> G[N];
int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0; i < n; i++){
		cin >> color[i];
		color[i]--;
	}
	for(int i = 0; i < m; i++){
		int v, u;
		cin >> v >> u;
		--v, --u;
		G[v].pb(u);
		G[u].pb(v);
		if(color[v]!=color[u]){
			int msk = (1<<color[v])|(1<<color[u]);
			dp[msk][v]++;
			dp[msk][u]++;
		}
	}
	for(int i=3; i <= k; i++){
		for(int j = 0; j < n; j++){
			for(int u : G[j]){
				for(int mask = 0; mask < (1<<k); mask++){
					if(__builtin_popcount(mask) != i)
						continue;
					if(!((1<<color[j])&mask))
						continue;
					dp[mask][j] += dp[mask^(1<<color[j])][u];
				}
			}
		}
	}
	int ans = 0;
	for(int i = 0; i < n; i++){
		for(int mask = 0; mask < (1<<k); mask++){
			ans += dp[mask][i];
		}
	}
	cout << ans;
}

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