Submission #830630

#	Time	Username	Problem	Language	Result	Execution time	Memory
830630		Johann	Paths (BOI18_paths)	C++14	100 / 100	374 ms	51916 KiB

paths

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

#define ll long long
#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vvi vector<vi>
#define tiii tuple<int,int,int>
#define vtiii vector<tiii>

#define F0R(i, n) for(int i = 0; i < (n); ++i)
#define R0F(i, n) for(int i = (n)-1; i >= 0; --i)
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#define nl "\n";


vvi Helper;
void initHelper(int K) {
    Helper.resize(K+1);
    for (int i = 0; i < K; ++i) Helper[1].push_back(1 << i);
    for (int i = 2; i <= K; ++i) {
        for (int x : Helper[i-1]) {
            for (int j = 32 - __builtin_clz(x); j < K; ++j) {
                Helper[i].push_back(x | (1<<j));
            }
        }
    }
}

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

    int N, M, K;
    cin >> N >> M >> K;
    initHelper(K);
    vvi adj(N);
    vi color(N);
    int k, a,b;
    F0R(i,N) { cin >> k; --k; color[i] = 1 << k; }
    F0R(i,M) {
        cin >> a >> b;
        --a; --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vvi dp(N, vi(1<<K, 0));
    for (int v = 0; v < N; ++v) ++dp[v][color[v]];
    ll ans = 0;
    for (k = 2; k <= K; ++k) {
        for (int v = 0; v < N; ++v) {
            for (int u : adj[v]) {
                for (int code : Helper[k-1]) {
                    if ((code & color[v]) > 0) continue;
                    dp[v][code | color[v]] += dp[u][code];
                }
            }
            for (int code : Helper[k]) ans += dp[v][code];
        }
    }
    cout << ans << endl;
}

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