Submission #1177895

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177895		ezzzay	Paths (BOI18_paths)	C++20	100 / 100	501 ms	269808 KiB

paths

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define pb push_back
const int N=3e5+5;
vector<int>v[N];
map<int,int>mp[N];
int c[N];
int dp[N][100];
signed main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>c[i];
        c[i]--;
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        v[a].pb(b);
        v[b].pb(a);
    }
    for(int i=0;i<(1<<k);i++){
        for(int a=1;a<=n;a++){
            if(i == (1<<c[a])){
                dp[a][i]=1;
            }
            if(i & (1<<c[a])){
                for(auto b:v[a]){
                    dp[a][i]+=dp[b][i- (1<<c[a])];
                }
            }
        } 
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<100;j++){
            ans+=dp[i][j];
        }
    }
    cout<<ans-n;
    
}

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