Submission #872818

#	Time	Username	Problem	Language	Result	Execution time	Memory
872818		tvladm2009	Paths (BOI18_paths)	C++17	100 / 100	357 ms	110244 KiB

paths

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

#define sz(x) (x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using db = long double;  // or double, if TL is tight
using str = string;
using ii = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

struct tree {
    const int SIGMA = 5;
    int n;
    vector<vector<int>> L;
    vector<int> Cul;
    vector<vector<int64_t>> DP;

    tree(int N, vector<int> c) : n(N), L(N), DP(N + 1, vector<int64_t>(1 << SIGMA, 0)), Cul(c) {}

    void add_edge(int x, int y) {
        L[x].push_back(y);
        L[y].push_back(x);
    }

    int64_t solve(int k) {
//        for(int i = 0; i < n; i++)
//            cout << Cul[i] << " ";
//        cout << "\n";
        int64_t res = 0;
        for(int mask = 1; mask < (1 << k); ++mask) {
            for(int i = 0; i < n; ++i) {
                if(mask & (1 << Cul[i])) {
                    if(mask ^ (1 << Cul[i]))
                        for(auto v : L[i])
                            DP[i][mask] += DP[v][mask ^ (1 << Cul[i])];
                    else  DP[i][mask] = 1;
                }
                res += DP[i][mask];
            }
        }
        return res;
    }
};


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

    int n, m, k;
    cin >> n >> m >> k;
    vector<int> c(n);
    for(int i = 0; i < n; ++i) {
        cin >> c[i];
        --c[i];
    }
    tree T(n, c);
    for(int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        T.add_edge(x, y);
    }
    cout << T.solve(k) - n << "\n";
    return 0;
}

Compilation message (stderr)

paths.cpp: In constructor 'tree::tree(int, std::vector<int>)':
paths.cpp:23:29: warning: 'tree::DP' will be initialized after [-Wreorder]
   23 |     vector<vector<int64_t>> DP;
      |                             ^~
paths.cpp:22:17: warning:   'std::vector<int> tree::Cul' [-Wreorder]
   22 |     vector<int> Cul;
      |                 ^~~
paths.cpp:25:5: warning:   when initialized here [-Wreorder]
   25 |     tree(int N, vector<int> c) : n(N), L(N), DP(N + 1, vector<int64_t>(1 << SIGMA, 0)), Cul(c) {}
      |     ^~~~

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