제출 #1191163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1191163		weakweakweak	Paths (BOI18_paths)	C++20	100 / 100	283 ms	107172 KiB

paths

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

int n, m, k, c[310000];
long long dp[310000][35] = {0}, ans = 0;
vector<int> e[510000];
int u[310000], v[311000];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        c[i]--;
    }
    for (int i = 1; i <= m; i++) {
        cin >> u[i] >> v[i];
        e[u[i]].push_back(v[i]);
        e[v[i]].push_back(u[i]);
    }
    for (int i = 1; i <= n; i++) dp[i][(1<<c[i])] = 1;
    for (int b = 2; b <= n; b++) {
        for (int mask = 0; mask < (1<<k); mask++) {
            if (__builtin_popcount(mask) != b-1) continue;
            for (int i = 1; i <= m; i++) {
                if (( (1<<c[v[i]]) & mask ) == 0) {
                    dp[v[i]][mask|(1<<c[v[i]])] += dp[u[i]][mask];
                }
                if (( (1<<c[u[i]]) & mask ) == 0) {
                    dp[u[i]][mask|(1<<c[u[i]])] += dp[v[i]][mask];
                }
            }
        }
    }
    for (int mask = 0; mask < (1<<k); mask++) {
        if (__builtin_popcount(mask) >= 2) {
            for (int i = 1; i <= n; i++) ans += dp[i][mask];
        }
    }
    cout << ans << '\n';
}

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