oj.uz

Submission #392898

# Submission time Handle Problem Language Result Execution time Memory
392898 2021-04-22T09:00:36 Z arujbansal Paths (BOI18_paths) C++17
23 / 100
 309 ms 30832 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <array>
#include <stack>
#include <queue>
#include <random>
#include <numeric>
#include <functional>
#include <chrono>
#include <utility>
#include <iomanip>
#include <assert.h>

using namespace std;

void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail>
void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
#define dbg(...) cerr << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)

#define rng_init mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define rng_seed(x) mt19937 rng(x)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
// #define int long long

const int MXN = 1e5 + 5, INF = 1e9 + 5;

void solve() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<vector<int>> dp(1 << K, vector<int>(N, 0));
    vector<int> colour(N);

    for (int i = 0; i < N; i++) {
        cin >> colour[i];
        colour[i]--;

        dp[1 << colour[i]][i] = 1;
    }

    vector<int> g[N];
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;

        g[u].push_back(v);
        g[v].push_back(u);
    }

    int ans = 0;

    for (int mask = 0; mask < (1 << K); mask++) {
        for (int u = 0; u < N; u++) {
            if ((mask >> colour[u]) & 1) {
                for (const auto &v : g[u])
                    dp[mask][u] += dp[mask ^ (1 << colour[u])][v];

                ans += dp[mask][u]; 
            }
        }
    }

    cout << ans - N;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int TC = 1;
    // cin >> TC;
    while (TC--) solve();
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 6980 KB Output is correct
2 Correct 58 ms 6116 KB Output is correct
3 Correct 309 ms 30832 KB Output is correct
4 Correct 104 ms 9284 KB Output is correct
5 Correct 106 ms 9076 KB Output is correct
6 Incorrect 196 ms 23216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 72 ms 6980 KB Output is correct
12 Correct 58 ms 6116 KB Output is correct
13 Correct 309 ms 30832 KB Output is correct
14 Correct 104 ms 9284 KB Output is correct
15 Correct 106 ms 9076 KB Output is correct
16 Incorrect 196 ms 23216 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 23 ms 2124 KB Output isn't correct
3 Halted 0 ms 0 KB -