Submission #473659

#	Time	Username	Problem	Language	Result	Execution time	Memory
473659		Sarah_Mokhtar	Paths (BOI18_paths)	C++14	100 / 100	911 ms	472912 KiB

paths

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define read freopen("acpc.in","r",stdin);
#define LESSGO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const ll N=3e5+10,M=505,OO=1e16,mod=1e9+9;
int n,m,k,col[N];
vector<int>adj[N];
ll dp[N][1<<6][3];
ll solve(int src,int msk,int cnt){
    ll& ret=dp[src][msk][cnt];
    if(~ret) return ret;
    ret=(cnt==2);
    for(int i:adj[src]){
        if(msk&(1ll<<col[i])) continue;
        ret+=solve(i,msk|(1ll<<col[i]),cnt+(cnt==1));
    }
    return ret;

}
int main(){
    memset(dp,-1,sizeof dp);
    cin>>n>>m>>k;
    for(int i=0;i<n;++i) cin>>col[i];
    while(m--){
        int u,v; cin>>u>>v;
        --u,--v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        
    }
    ll ans=0;
    for(int i=0;i<n;++i){
        ans+=solve(i,1<<col[i],1);
    }
    cout<<ans<<'\n';

}

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