제출 #1015759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1015759		phoenix	Paths (BOI18_paths)	C++17	100 / 100	313 ms	70736 KiB

paths

#include <bits/stdc++.h>

using namespace std;

const int N = 300100;

int n, m, k;
vector<int> g[N];
int color[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
        color[i]--;
    }
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> ord((1 << k) - 1);
    iota(ord.begin(), ord.end(), 1);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return __builtin_popcount(a) <= __builtin_popcount(b);
    });

    vector<vector<long long>> dp(n + 1, vector<long long>(1 << k));
    for (int i = 1; i <= n; i++) {
        dp[i][(1 << color[i])] = 1;
    }
    for (int msk : ord) {
        for (int v = 1; v <= n; v++) {
            for (int to : g[v]) {
                if (msk >> color[to] & 1) continue;
                dp[to][msk | (1 << color[to])] += dp[v][msk];
            }
        }
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int msk = 1; msk < (1 << k); msk++) {
            if (__builtin_popcount(msk) < 2) continue;
            ans += dp[i][msk];
        }
    }
    cout << ans;
}

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