Submission #62748

#	Time	Username	Problem	Language	Result	Execution time	Memory
62748		MatheusLealV	Paths (BOI18_paths)	C++17	100 / 100	922 ms	273176 KiB

paths

#include <bits/stdc++.h>
#define N 300010
#define M 70
using namespace std;
typedef long long ll;

int n, m, k, c[N];

ll dp[N][M];

vector<int> grafo[N];

ll solve(int x, int mask)
{
    ll ans = 1LL;

    if(dp[x][mask] != -1) return dp[x][mask];

    for(auto v: grafo[x])
    {
        if(mask & (1<<c[v])) continue;

        ans += solve(v, mask | (1<<c[v]));
    }

    return dp[x][mask] = ans;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    cin>>n>>m>>k;

    for(int i = 1; i <= n; i++) cin>>c[i];

    for(int i = 1, a, b; i <= m; i++)
    {
        cin>>a>>b;

        grafo[a].push_back(b);

        grafo[b].push_back(a);
    }

    memset(dp, -1, sizeof dp);

    ll ans = 0;

    for(int i = 1; i <= n; i++) ans += solve(i, 1<<c[i]);

    cout<<ans - n<<"\n";
}

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