Submission #1072903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072903		fatman87878	Paths (BOI18_paths)	C++17	100 / 100	325 ms	97104 KiB

paths

#include<bits/stdc++.h>
using namespace std;
#define IOS cin.tie(nullptr)->sync_with_stdio(0),cin.exceptions(cin.failbit);
#define lb(x) (x)&-(x)
#define all(x) (x).begin(),(x).end()
#define ll long long

constexpr int maxN=3e5+5;

int n,m,k,col[maxN];

ll dp[maxN][1<<5],ans;

vector<int> adj[maxN];

int main(){
    cin>>n>>m>>k;
    for(int i = 1;i<=n;i++)cin>>col[i],--col[i],dp[i][1<<col[i]]=1;
    for(int a,b;m--;)cin>>a>>b,adj[adj[b].emplace_back(a)].emplace_back(b);
    for(int mask = 0;mask<1<<k;mask++)for(int i = 1;i<=n;i++)if(mask>>col[i]&1)for(int j:adj[i])dp[i][mask]+=dp[j][mask^(1<<col[i])];
    for(int mask = 0;mask<1<<k;mask++)for(int i = 1;i<=n;i++)if(__builtin_popcount(mask)>1)ans+=dp[i][mask];
    cout<<ans;
}

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