Submission #1091577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091577		gyg	Paths (BOI18_paths)	C++17	100 / 100	490 ms	30232 KiB

paths

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array
#define vct vector
const int MX_N = 3e5 + 5, MX_K = 5 + 5;

int n, m, k;
arr<int, MX_N> cl;
arr<vct<int>, MX_N> adj;

vct<int> ord;
set<vct<int>> ords;
void bcktr(int i = 1) {
    if (i == k + 1) {
        if (ord.size() <= 1) return;
        ords.insert(ord);
        return;
    }

    bcktr(i + 1);
    for (int j = 1; j <= k; j++) {
        if (count(ord.begin(), ord.end(), j)) continue;
        ord.push_back(j);
        bcktr(i + 1);
        ord.pop_back();
    }
}
arr<vct<int>, MX_K> cl_nds;
void prcmp() {
    bcktr();
    // for (vct<int> x : ords) {
    //     for (int y : x) cout << y << " ";
    //     cout << endl;
    // }
    for (int u = 1; u <= n; u++) cl_nds[cl[u]].push_back(u);
}

arr<int, MX_N> dp;
int cmp() {
    int ans = 0;
    for (vct<int> x : ords) {
        fill(dp.begin(), dp.end(), 0);
        int nw_ans = 0;

        for (int i = 0; i < x.size(); i++) {
            for (int u : cl_nds[x[i]]) {
                if (i == 0) { dp[u] = 1; continue; }
                for (int v : adj[u])
                    if (cl[v] == x[i - 1]) dp[u] += dp[v];
            }
        }

        for (int u : cl_nds[x.back()]) nw_ans += dp[u];
        ans += nw_ans;

        // for (int y : x) cout << y << " ";
        // cout << ": " << nw_ans << endl;
    }
    return ans;
}

signed main() {
    // freopen("pth.in", "r", stdin);
    cin >> n >> m >> k;
    for (int u = 1; u <= n; u++) cin >> cl[u];
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v), adj[v].push_back(u);
    }

    prcmp();
    int ans = cmp();
    cout << ans << endl;

}

Compilation message (stderr)

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

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