Submission #413824

#TimeUsernameProblemLanguageResultExecution timeMemory
413824ak2006Paths (BOI18_paths)C++14
23 / 100
3068 ms98984 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vb = vector<bool>; using vvb = vector<vb>; using vc = vector<char>; using vvc = vector<vc>; #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define pb push_back void setIO() { fast; } int n = 3e5 + 5,m = 3e5 + 5,k = 5; vvi adj(n); vi col(n); vvl dp(n,vl(1<<k)); void dfs(int u,int mask) { int mask2 = mask | (1<<col[u]); dp[u][mask] = 1; for (int v:adj[u]){ if ((mask2 & (1<<col[v])))continue; dfs(v,mask2); dp[u][mask] += dp[v][mask2]; } } int main() { setIO(); cin>>n>>m>>k; for (int i = 1;i<=n;i++){cin>>col[i];col[i]--;} while (m--){ int u,v; cin>>u>>v; adj[u].pb(v),adj[v].pb(u); } ll ans = 0; for (int i = 1;i<=n;i++){ for (int mask = 0;mask < (1<<k);mask++){ if (mask & (1<<col[i]))continue; dfs(i,mask); if (mask == 0)ans += dp[i][0] - 1; } } cout<<ans; 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...