Submission #532024

#	Time	Username	Problem	Language	Result	Execution time	Memory
532024		hohohaha	Paths (BOI18_paths)	C++14	100 / 100	688 ms	100396 KiB

paths

#include<bits/stdc++.h>

using namespace std;

#define fori(i, l, r) for(int i = (int) (l); i <= (int) (r); i++) 
#define ford(i, r, l) for(int i = (int) (r); i >= (int) (l); i--) 
#define ii pair<int, int> 
#define fi first
#define se second
#define vi vector<int> 
#define eb emplace_back
#define sp ' '
#define endl '\n'
#define int long long

mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count()); 
const int maxn = 3e5 + 5; 
int n, m, k, ans;
int c[maxn];  
vi g[maxn]; 
int dp[maxn][1 << 5]; 
signed main() { 
//	freopen("Paths.inp", "r", stdin); 
//	freopen("Paths.out", "w", stdout); 
	ios_base::sync_with_stdio(0);
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m >> k; 
	fori(i, 1, n) { 
		cin >> c[i]; 
		c[i]--; 
	}
	fori(i, 1, m) { 
		int u, v; cin >> u >> v; 
		g[u].eb(v); 
		g[v].eb(u); 
	}
	fori(i, 1, n) { 
		dp[i][1 << c[i]] = 1; 
	}
	fori(mask, 1, (1 << k) - 1) { 
		fori(i, 1, n) { 
			for(int j: g[i]) { 
				if(!(mask >> c[j] & 1)) { 
					dp[j][mask ^ (1 << c[j])] += dp[i][mask]; 
				}
			}
		}
	}
	fori(i, 1, n) { 
		fori(mask, 1, (1 << k) - 1) { 
			if(__builtin_popcountll(mask) >= 2) ans += dp[i][mask]; 
		}
	}
	cout << ans; 
}

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