Submission #319320

#	Time	Username	Problem	Language	Result	Execution time	Memory
319320		OttoTheDino	Paths (BOI18_paths)	C++17	100 / 100	527 ms	153364 KiB

paths

#include <bits/stdc++.h>
using namespace std;

#define rep(n)      for (int i = 0; i < n; ++i)
#define rep2(n)     for (int j = 0; j < n; ++j)
#define mp          make_pair
#define pb          push_back
#define fi          first
#define se          second
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<double, double> dd;

const int mxn = 5e5+5, mxa = 32;

ll dp[mxn][mxa], col[mxn];
vi neibs[mxn];

ll f (int c, int C) {
    if (dp[c][C]!=-1) return dp[c][C];
    ll res = C!=0, cur = C|(1<<col[c]);
    for (int v : neibs[c]) if (((1<<col[v])&cur)==0) res += f (v, cur);
    dp[c][C] = res;
    return res;
}

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

    memset(dp, -1, mxn*mxa*sizeof(ll));
    int n, m, k, a, b;
    cin >> n >> m >> k;
    rep (n) {
       cin >> col[i];
       col[i]--;
    }
    rep (m) {
        cin >> a >> b;
        neibs[a-1].pb(b-1);
        neibs[b-1].pb(a-1);
    }
    
    ll ans = 0;
    rep (n) ans += f(i, 0);

    cout << ans << "\n";

    return 0;
}

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