Submission #464006

#	Time	Username	Problem	Language	Result	Execution time	Memory
464006		bonopo	Paths (BOI18_paths)	C++14	100 / 100	591 ms	97108 KiB

paths

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=3e5+5, MOD=1e9+7, LOG=19;
int N, M, K, c[MM]; ll dp[32][MM], ans;
vector<int> adj[MM];

ll dfs(int u, int mask) {
    if((mask&(1<<c[u]))==0) return 0;

    ll &ret=dp[mask][u];
    if(~ret) return ret;

    ret=0;
    for(int &v:adj[u]) if(mask&(1<<c[v])) ret+=+dfs(v, mask^(1<<c[u]));
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>M>>K;
    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=N; ++i) cin>>c[i], --c[i], dp[1<<c[i]][i]=1;
    for(int i=1, u, v; i<=M; ++i) {
        cin>>u>>v;
        adj[u].pb(v); adj[v].pb(u); }
    for(int i=1; i<=N; ++i) for(int k=0; k<(1<<K); ++k) ans+=dfs(i, k);
    cout<<ans-N<<el;
}

// MM

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