Submission #768658

#	Time	Username	Problem	Language	Result	Execution time	Memory
768658		Tenis0206	Paths (BOI18_paths)	C++11	100 / 100	348 ms	104232 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int nmax = 3e5;

int n,m,k;
int c[nmax + 5];

long long dp[nmax + 5][35];
bool sel[nmax + 5][35];

vector<int> G[nmax + 5];

long long Back(int nod, int mask)
{
    if(sel[nod][mask])
    {
        return dp[nod][mask];
    }
    if(__builtin_popcount(mask)==1)
    {
        return dp[nod][mask] = 1;
    }
    int new_mask = mask - (1<<c[nod]);
    for(auto it : G[nod])
    {
        if((new_mask & (1<<c[it])) == 0)
        {
            continue;
        }
        dp[nod][mask] += Back(it,new_mask);
    }
    sel[nod][mask] = true;
    return dp[nod][mask];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m>>k;
    for(int i=1; i<=n; i++)
    {
        cin>>c[i];
        --c[i];
    }
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    long long rez = 0;
    for(int mask=0; mask<(1<<k); mask++)
    {
        for(int nod=1; nod<=n; nod++)
        {
            if((mask & (1<<c[nod]))==0)
            {
                continue;
            }
            if(__builtin_popcount(mask)==1)
            {
                dp[nod][mask] = 1;
                continue;
            }
            int new_mask = mask - (1<<c[nod]);
            for(auto it : G[nod])
            {
                dp[nod][mask] += dp[it][new_mask];
            }
            rez += dp[nod][mask];
        }
    }
    cout<<rez<<'\n';
    return 0;
}

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