Submission #1121904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121904		_callmelucian	Paths (BOI18_paths)	C++14	100 / 100	315 ms	98444 KiB

paths

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

typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pl;
typedef pair<int,int> pii;
typedef tuple<int,int,int> tpl;

#define all(a) a.begin(), a.end()
#define filter(a) a.erase(unique(all(a)), a.end())

const int mn = 3e5 + 5;
ll dp[mn][1 << 5], color[mn];
vector<int> adj[mn];

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

    int n, m, k; cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
        color[i]--;
    }
    while (m--) {
        int a, b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++) dp[i][1 << color[i]]++;
    for (int mask = 0; mask < (1 << k); mask++) {
        if (__builtin_popcount(mask) <= 1) continue;
        for (int u = 1; u <= n; u++) {
            for (int v : adj[u]) dp[u][mask] += dp[v][mask ^ (1 << color[u])];
            ans += dp[u][mask];
        }
    }
    cout << ans;

    return 0;
}

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