Submission #399353

#	Time	Username	Problem	Language	Result	Execution time	Memory
399353		iulia13	Paths (BOI18_paths)	C++14	100 / 100	1012 ms	66848 KiB

paths

#include <iostream>
#include <vector>
using namespace std;
#define ll long long
const int nmax = 3e5 + 5;
int color[nmax];
vector<vector<ll>> dp;
vector <int> g[nmax];
///dp[nod][msk] -> din nodul nod un lant care are culorile din msk o sg data
ll dfs(ll nod, ll msk = 0)
{
    if (dp[nod][msk] != -1)
        return dp[nod][msk];
    if (msk & (1 << color[nod]))
    {
        dp[nod][msk] = 0;
        return 0;
    }
    dp[nod][msk] = 1;
    for (auto x : g[nod])
        dp[nod][msk] += dfs(x, msk + (1 << color[nod]));
    return dp[nod][msk];
}
int main()
{
    int n, m, k, i;
    ll ans = 0;
    cin >> n >> m >> k;
    for (i = 0; i < n; i++)
        cin >> color[i], color[i]--;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dp.resize(n);
    for (i = 0; i < n; i++)
        dp[i].resize((1 << k), -1);
    for (i = 0; i < n; i++)
        ans += dfs(i);
    cout << ans - n;
    return 0;
}

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