Submission #642698

#TimeUsernameProblemLanguageResultExecution timeMemory
642698andreast12Paths (BOI18_paths)C++17
100 / 100
423 ms24820 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define fi first #define se second #define pb push_back const int mod=1e9+7, maxn=3e5+5; int n, m, k, c[maxn], u, v, tmp, order[125][10], p[10], NEXT[10], now; vector<int> adj[maxn]; bool vis[10]; ll byk[maxn], tot[10], ans; queue<int> q; string s; map<string, bool> pernah; void perm(int idx) { if(idx>k) { tmp++; for(int i=1; i<=k; i++) order[tmp][i]=p[i]; return; } for(int i=1; i<=k; i++) { if(!vis[i]) { vis[i]=true; p[idx]=i; perm(idx+1); vis[i]=false; } } } 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]; while(m--) { cin >> u >> v; adj[u].pb(v); adj[v].pb(u); } perm(1); for(int i=1; i<=tmp; i++) { for(int j=1; j<=k; j++) NEXT[order[i][j]]=order[i][j+1], tot[j]=0; for(int j=1; j<=n; j++) { if(c[j]==order[i][1]) { q.push(j); byk[j]=1; } else byk[j]=-1; } while(!q.empty()) { now=q.front(); tot[c[now]]+=byk[now]; q.pop(); for(auto nxt:adj[now]) { if(c[nxt]==NEXT[c[now]]) { if(byk[nxt]==-1) { byk[nxt]=byk[now]; q.push(nxt); } else byk[nxt]+=byk[now]; } } } s=order[i][1]-'0'; for(int j=2; j<=k; j++) { s+=order[i][j]-'0'; if(!pernah[s]) { ans+=tot[order[i][j]]; pernah[s]=true; } } } cout << ans << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...