Submission #1192432

#TimeUsernameProblemLanguageResultExecution timeMemory
1192432julia_08Paths (BOI18_paths)C++20
100 / 100
842 ms26432 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int MAXN = 3e5 + 10; int color[MAXN]; vector<int> adj[MAXN]; ll dp[5][MAXN]; int n, m; ll solve(vector<int> c){ ll r = 0; int K = (int) c.size(); do{ for(int k=0; k<K; k++){ for(int i=1; i<=n; i++){ dp[k][i] = 0; if(k == K - 1 && color[i] == c[k]) dp[k][i] = 1; } } for(int k=K-2; k>=0; k--){ for(int i=1; i<=n; i++){ if(color[i] == c[k]){ for(auto j : adj[i]){ if(color[j] == c[k + 1]){ dp[k][i] += dp[k + 1][j]; } } } if(k == 0) r += dp[k][i]; } } } while(next_permutation(c.begin(), c.end())); return r; } int main(){ cin.tie(0)->sync_with_stdio(0); int k; cin >> n >> m >> k; for(int i=1; i<=n; i++) cin >> color[i]; for(int i=1; i<=m; i++){ int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } ll ans = 0; for(int a=1; a<=k; a++){ for(int b=a+1; b<=k; b++){ ans += solve({a, b}); for(int c=b+1; c<=k; c++){ ans += solve({a, b, c}); for(int d=c+1; d<=k; d++){ ans += solve({a, b, c, d}); for(int e=d+1; e<=k; e++){ ans += solve({a, b, c, d, e}); } } } } } cout << ans << "\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...