Submission #1265962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265962		warrenn	Paths (BOI18_paths)	C++20	100 / 100	432 ms	96024 KiB

paths

#include<bits/stdc++.h>
using namespace std;
#define int long long 

int n,m,k;
int dp[300002][32];
int col[300002];
vector<int>adj[300002];

signed main(){
    cin>>n>>m>>k;
    for(int q=1;q<=n;q++){
        cin>>col[q];
        col[q]--;
        dp[q][(1<<col[q])]=1;
    }
    for(int q=1;q<=m;q++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int ans=0;
    for(int mask=0;mask<(1<<k);mask++){
        for(int idx=1;idx<=n;idx++){
            for(auto nxt : adj[idx]){
                if((mask>>col[nxt])&1){

                }
                else{
                    dp[nxt][mask+(1<<col[nxt])]+=dp[idx][mask];
                }
            }
            ans+=dp[idx][mask];
        }
    }
    cout<<ans-n<<endl;
}

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