oj.uz

Submission #1111702

# Submission time Handle Problem Language Result Execution time Memory
1111702 2024-11-12T16:55:30 Z ortsac Paths (BOI18_paths) C++17
53 / 100
 484 ms 11608 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

int n, m, k;
vector<int> ord;
const int MAXN = 1e5 + 10;
vector<int> adj[MAXN];
int cor[MAXN];
int dp[MAXN];
int t;

void calc(int node, int i) {
    if (dp[node] != -1) return;
    if (i == (t - 1)) {
        dp[node] = 1;
        return;
    }
    dp[node] = 0;
    for (auto u : adj[node]) {
        if (cor[u] == ord[i + 1]) {
            calc(u, i + 1);
            dp[node] += dp[u];
        }
    }
}

int32_t main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        cin >> cor[i];
    }
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int ans = 0;
    for (int mask = 1; mask < (1LL << k); mask++) {
        ord.clear();
        for (int i = 0; i < k; i++) {
            if (mask & (1LL << i)) ord.push_back(i + 1);
        }
        t = ord.size();
        if (t == 1) continue;
        do {
            // do it now!!
            //for (auto u : ord) cout << u << " ";
            //cout << "\n";
            int currans = 0;
            memset(dp, -1, sizeof dp);
            for (int i = 1; i <= n; i++) {
                if (cor[i] == ord[0]) {
                    calc(i, 0);
                    currans += dp[i];
                }
            }
            //cout << "ans " << currans << "\n";
            ans += currans;
        } while (next_permutation(ord.begin(), ord.end()));
    }
    cout << ans << "\n";
}

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 11608 KB Output is correct
2 Correct 99 ms 10568 KB Output is correct
3 Runtime error 31 ms 6736 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3408 KB Output is correct
2 Correct 4 ms 3408 KB Output is correct
3 Correct 3 ms 3408 KB Output is correct
4 Correct 3 ms 3408 KB Output is correct
5 Correct 2 ms 2808 KB Output is correct
6 Correct 4 ms 3408 KB Output is correct
7 Correct 5 ms 3408 KB Output is correct
8 Correct 4 ms 3408 KB Output is correct
9 Correct 4 ms 3408 KB Output is correct
10 Correct 3 ms 3408 KB Output is correct
11 Correct 121 ms 11608 KB Output is correct
12 Correct 99 ms 10568 KB Output is correct
13 Runtime error 31 ms 6736 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3408 KB Output is correct
2 Correct 164 ms 5712 KB Output is correct
3 Correct 34 ms 6448 KB Output is correct
4 Correct 87 ms 9200 KB Output is correct
5 Correct 68 ms 9616 KB Output is correct
6 Correct 482 ms 9204 KB Output is correct
7 Correct 57 ms 6472 KB Output is correct
8 Correct 159 ms 9180 KB Output is correct
9 Correct 101 ms 9404 KB Output is correct
10 Correct 122 ms 9256 KB Output is correct
11 Correct 314 ms 7616 KB Output is correct
12 Correct 215 ms 8536 KB Output is correct
13 Correct 298 ms 7820 KB Output is correct
14 Correct 484 ms 9192 KB Output is correct
15 Correct 467 ms 9288 KB Output is correct
16 Correct 5 ms 3408 KB Output is correct
17 Correct 4 ms 3352 KB Output is correct
18 Correct 3 ms 3408 KB Output is correct
19 Correct 3 ms 3408 KB Output is correct
20 Correct 2 ms 2640 KB Output is correct
21 Correct 4 ms 3408 KB Output is correct
22 Correct 4 ms 3408 KB Output is correct
23 Correct 4 ms 3408 KB Output is correct
24 Correct 4 ms 3576 KB Output is correct
25 Correct 3 ms 3564 KB Output is correct