Submission #1173599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173599		AlgorithmWarrior	Paths (BOI18_paths)	C++20	100 / 100	362 ms	99856 KiB

paths

#include <bits/stdc++.h>

using namespace std;

int const MAX=3e5+5;
long long dp[MAX][35];
vector<int>G[MAX];
int n,m,k;
int color[MAX];

void read(){
    cin>>n>>m>>k;
    int i;
    for(i=1;i<=n;++i){
        cin>>color[i];
        --color[i];
        dp[i][1<<color[i]]=1;
    }
    for(i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
}

long long get_dp(){
    long long sum=0;
    int i,j;
    for(j=1;j<(1<<k);++j){
        for(i=1;i<=n;++i)
            if(j&(1<<color[i])){
                for(auto vec : G[i])
                    dp[i][j]+=dp[vec][j^(1<<color[i])];
                sum+=dp[i][j];
            }
    }
    return sum-n;
}

int main()
{
    read();
    cout<<get_dp();
    return 0;
}

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