Submission #869373

#	Time	Username	Problem	Language	Result	Execution time	Memory
869373		12345678	Paths (BOI18_paths)	C++17	100 / 100	362 ms	98388 KiB

paths

#include <bits/stdc++.h>

using namespace std;

#define ll long long

const int nx=3e5+5;
ll n, m, k, u, v, c[nx], dp[nx][32], ans;
vector<int> d[nx];


int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n>>m>>k;
    for (int i=1; i<=n; i++) cin>>c[i], c[i]--;
    for (int i=0; i<m; i++) cin>>u>>v, d[u].push_back(v), d[v].push_back(u);
    for (int i=1; i<(1<<k); i++) 
    {
        for (int j=1; j<=n; j++)
        {
            if (!(i&(1<<c[j]))) continue;
            if (__builtin_popcount(i)==1) dp[j][i]++;
            for (auto v:d[j]) dp[j][i]+=dp[v][i-(1<<c[j])];
            ans+=dp[j][i];
        }
    }
    cout<<ans-n;
}

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