Submission #953174

#	Time	Username	Problem	Language	Result	Execution time	Memory
953174		asdasdqwer	Paths (BOI18_paths)	C++14	100 / 100	382 ms	97496 KiB

paths

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

const int MAXN = 300000;

int n,m,k;
vector<vector<int>> g;
int c[MAXN];

long long res = 0;
long long dp[MAXN][32];

void edit(int node, int num) {
    for (int i=0;i<(1<<k);i++) {
        if (((1<<c[node])&i) == 0) continue;
        if (__builtin_popcount(i) != num) continue;

        for (int x:g[node]) {
            dp[node][i] += dp[x][(i ^ (1<<c[node]))];
        }
    }
}

void all(int num) {
    for (int i=0;i<n;i++) {
        edit(i, num);
    }
}

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

    cin>>n>>m>>k;
    for (int i=0;i<n;i++) {
        cin>>c[i];c[i]--;
    }

    g.resize(n);
    for (int i=0;i<m;i++) {
        int a,b;cin>>a>>b;a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    for (int i=0;i<n;i++) {
        dp[i][(1<<c[i])] = 1;
    }

    for (int i=2;i<=k;i++) {
        all(i);
    }

    for (int i=0;i<n;i++) {
        for (int j=0;j<32;j++) {
            res += dp[i][j];
        }
    }

    res -= n;

    cout<<res<<"\n";
}

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