Submission #1091354

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091354		MateiKing80	Paths (BOI18_paths)	C++14	100 / 100	359 ms	70884 KiB

paths

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<int> vec[300100];
int color[300100];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.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;
        vec[u].push_back(v);
        vec[v].push_back(u);
    }
    vector<int> ord((1 << k) - 1);
    for(int i = 0; i < ord.size(); i ++)
        ord[i] = i + 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 : vec[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;
}

Compilation message (stderr)

paths.cpp: In function 'int main()':
paths.cpp:28:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0; i < ord.size(); i ++)
      |                    ~~^~~~~~~~~~~~

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