Submission #751670

#	Time	Username	Problem	Language	Result	Execution time	Memory
751670		bgnbvnbv	Paths (BOI18_paths)	C++14	100 / 100	504 ms	188720 KiB

paths

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,a[maxN];
vector<ll>g[maxN];
ll dp[maxN][1<<5];
ll k;
vector<ll>vec[maxN][6];
void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) cin >> a[i],a[i]--;
    for(int i=1;i<=m;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][1<<a[i]]=1;
        for(int j=0;j<(1<<k);j++)
        {
            if(j>>a[i]&1)
            {
                vec[i][__builtin_popcount(j)].pb(j);
            }
        }
    }
    for(int q=2;q<=k;q++)
    {
        for(int i=1;i<=n;i++)
        {
            for(auto j:g[i])
            {
                for(auto vc:vec[i][q])
                {
                    dp[i][vc]+=dp[j][vc-(1<<a[i])];
                }
            }
        }
    }
    ll ans=0;
    for(int j=0;j<(1<<k);j++) for(int i=1;i<=n;i++) ans+=dp[i][j];
    ans-=n;
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

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