Submission #1156824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156824		the_ZHER	Paths (BOI18_paths)	C++20	100 / 100	213 ms	114788 KiB

paths

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=3e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int l,r;
};
vector<int>v[N];
vector<int>v1;
int dp[N][40];
signed main(){
boost;
    int n,m,k;
    cin>>n>>m>>k;
    v1.push_back(0);
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        x--;
        v1.push_back(x);
    }
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i=1;i<=n;i++){
        dp[i][(1ll<<v1[i])]++;
    }
    int ans=0;
    for(int i=0;i<(1ll<<k);i++){
        for(int j=1;j<=n;j++){
            if(dp[j][i]){
                for(int l=0;l<v[j].size();l++){
                    int x=v1[v[j][l]];
                    int z=v[j][l];
                    if(i&(1ll<<x)){
                        continue;
                    }
                    dp[z][i+(1ll<<x)]+=dp[j][i];
                }
            }
        }
        for(int j=1;j<=n;j++){
            ans+=dp[j][i];
        }
    }
    cout<<ans-n;
}  

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