oj.uz

Submission #838528

# Submission time Handle Problem Language Result Execution time Memory
838528 2023-08-27T10:36:25 Z vjudge1 Paths (BOI18_paths) C++14
100 / 100
 376 ms 97156 KB 
#include <queue>
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 10;
vector<int> graph[maxn];
ll dp[maxn][1 << 5];
int color[maxn];
ll dfs(int node, int bitmask, int length) {
    if(dp[node][bitmask] != -1) {
        return dp[node][bitmask];
    }
    ll res = 0;
    if(dp[node][bitmask] != -1) {
        return dp[node][bitmask];
    }
    if(length >= 2) {
        res++;
    }
    for(int neighbour : graph[node]) {
        if(!(bitmask & (1 << color[neighbour]))) {
            res += dfs(neighbour, bitmask | (1 << color[neighbour]), length + 1);
        }
    }
    return dp[node][bitmask] = res;
}
int main(int argc, const char * argv[]) {
    int n, m, k;
    cin >> n >> m >> k;
    
    for(int i = 0; i < n; i++) {
        cin >> color[i];
        color[i]--;
    }
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    memset(dp, -1, sizeof dp);
    ll res = 0;
    for(int i = 0; i < n; i++) {
        res += dfs(i, (1 << color[i]), 1);
    }
    cout << res << endl;
    return 0;
}

//4 3 3 1 2 1 3 1 2
//2 3
//4 2

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82380 KB Output is correct
2 Correct 30 ms 82416 KB Output is correct
3 Correct 30 ms 82400 KB Output is correct
4 Correct 30 ms 82440 KB Output is correct
5 Correct 36 ms 82452 KB Output is correct
6 Correct 35 ms 82472 KB Output is correct
7 Correct 30 ms 82388 KB Output is correct
8 Correct 30 ms 82528 KB Output is correct
9 Correct 31 ms 82380 KB Output is correct
10 Correct 30 ms 82480 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 86148 KB Output is correct
2 Correct 127 ms 88232 KB Output is correct
3 Correct 316 ms 96500 KB Output is correct
4 Correct 176 ms 90380 KB Output is correct
5 Correct 160 ms 90368 KB Output is correct
6 Correct 269 ms 94472 KB Output is correct
7 Correct 357 ms 96496 KB Output is correct
8 Correct 341 ms 97156 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82380 KB Output is correct
2 Correct 30 ms 82416 KB Output is correct
3 Correct 30 ms 82400 KB Output is correct
4 Correct 30 ms 82440 KB Output is correct
5 Correct 36 ms 82452 KB Output is correct
6 Correct 35 ms 82472 KB Output is correct
7 Correct 30 ms 82388 KB Output is correct
8 Correct 30 ms 82528 KB Output is correct
9 Correct 31 ms 82380 KB Output is correct
10 Correct 30 ms 82480 KB Output is correct
11 Correct 148 ms 86148 KB Output is correct
12 Correct 127 ms 88232 KB Output is correct
13 Correct 316 ms 96500 KB Output is correct
14 Correct 176 ms 90380 KB Output is correct
15 Correct 160 ms 90368 KB Output is correct
16 Correct 269 ms 94472 KB Output is correct
17 Correct 357 ms 96496 KB Output is correct
18 Correct 341 ms 97156 KB Output is correct
19 Correct 145 ms 88952 KB Output is correct
20 Correct 130 ms 88248 KB Output is correct
21 Correct 365 ms 96424 KB Output is correct
22 Correct 172 ms 90328 KB Output is correct
23 Correct 170 ms 90324 KB Output is correct
24 Correct 257 ms 94384 KB Output is correct
25 Correct 327 ms 96472 KB Output is correct
26 Correct 350 ms 97088 KB Output is correct
27 Correct 145 ms 88276 KB Output is correct
28 Correct 166 ms 89780 KB Output is correct
29 Correct 373 ms 96500 KB Output is correct
30 Correct 300 ms 92860 KB Output is correct
31 Correct 312 ms 92920 KB Output is correct
32 Correct 376 ms 96460 KB Output is correct
33 Correct 29 ms 82484 KB Output is correct
34 Correct 28 ms 82388 KB Output is correct
35 Correct 28 ms 82416 KB Output is correct
36 Correct 29 ms 82484 KB Output is correct
37 Correct 27 ms 82472 KB Output is correct
38 Correct 28 ms 82436 KB Output is correct
39 Correct 29 ms 82448 KB Output is correct
40 Correct 30 ms 82424 KB Output is correct
41 Correct 29 ms 82440 KB Output is correct
42 Correct 28 ms 82436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 82368 KB Output is correct
2 Correct 72 ms 84280 KB Output is correct
3 Correct 70 ms 84232 KB Output is correct
4 Correct 111 ms 86976 KB Output is correct
5 Correct 97 ms 87748 KB Output is correct
6 Correct 130 ms 86992 KB Output is correct
7 Correct 64 ms 84288 KB Output is correct
8 Correct 130 ms 86924 KB Output is correct
9 Correct 100 ms 87700 KB Output is correct
10 Correct 117 ms 87644 KB Output is correct
11 Correct 126 ms 85648 KB Output is correct
12 Correct 105 ms 86816 KB Output is correct
13 Correct 107 ms 85820 KB Output is correct
14 Correct 124 ms 87012 KB Output is correct
15 Correct 115 ms 87000 KB Output is correct
16 Correct 28 ms 82384 KB Output is correct
17 Correct 28 ms 82504 KB Output is correct
18 Correct 28 ms 82488 KB Output is correct
19 Correct 28 ms 82432 KB Output is correct
20 Correct 30 ms 82500 KB Output is correct
21 Correct 32 ms 82584 KB Output is correct
22 Correct 28 ms 82492 KB Output is correct
23 Correct 28 ms 82388 KB Output is correct
24 Correct 29 ms 82480 KB Output is correct
25 Correct 27 ms 82484 KB Output is correct