Submission #1112776

#TimeUsernameProblemLanguageResultExecution timeMemory
1112776kojacPaths (BOI18_paths)C++14
53 / 100
672 ms1048576 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll LINF = 0x3f3f3f3f3f3f3f3f; #define MAXN (int)(3e5+10) ll dp[MAXN][7][70], 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(auto u : g[j]){ dp[j][i][bm] += dp[u][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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...