oj.uz

Submission #870658

# Submission time Handle Problem Language Result Execution time Memory
870658 2023-11-08T17:49:23 Z TahirAliyev Paths (BOI18_paths) C++17
100 / 100
 377 ms 95156 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pii pair<int, int>
#define oo 1e18

const int MAX = 3e5 + 5;

vector<int> g[MAX];

ll dp[33][MAX];
int c[MAX];
int n, m, k;

ll rec(int node, int mask){
    mask |= (1 << c[node]);
    if(dp[mask][node] != -1) return dp[mask][node];
    ll ans = 0;
    if(__popcount(mask) >= 2) ans++;
    for(int to : g[node]){
        if(mask & (1 << c[to])){
            continue;
        }
        ans += rec(to, mask);
    }
    return dp[mask][node] = ans;
}

int main(){
    memset(dp, -1, sizeof(dp));
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> c[i];
        c[i]--;
    }
    for(int i = 1; i <= m; i++){
        int a, b; cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        ans += rec(i, 0);
    }
    cout << ans << '\n';
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 85852 KB Output is correct
2 Correct 11 ms 85852 KB Output is correct
3 Correct 11 ms 85900 KB Output is correct
4 Correct 11 ms 85852 KB Output is correct
5 Correct 11 ms 85852 KB Output is correct
6 Correct 11 ms 85852 KB Output is correct
7 Correct 11 ms 85852 KB Output is correct
8 Correct 11 ms 85852 KB Output is correct
9 Correct 11 ms 85852 KB Output is correct
10 Correct 11 ms 85916 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 89628 KB Output is correct
2 Correct 105 ms 89440 KB Output is correct
3 Correct 335 ms 94344 KB Output is correct
4 Correct 151 ms 90444 KB Output is correct
5 Correct 142 ms 90452 KB Output is correct
6 Correct 246 ms 93212 KB Output is correct
7 Correct 305 ms 94292 KB Output is correct
8 Correct 324 ms 95156 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 85852 KB Output is correct
2 Correct 11 ms 85852 KB Output is correct
3 Correct 11 ms 85900 KB Output is correct
4 Correct 11 ms 85852 KB Output is correct
5 Correct 11 ms 85852 KB Output is correct
6 Correct 11 ms 85852 KB Output is correct
7 Correct 11 ms 85852 KB Output is correct
8 Correct 11 ms 85852 KB Output is correct
9 Correct 11 ms 85852 KB Output is correct
10 Correct 11 ms 85916 KB Output is correct
11 Correct 127 ms 89628 KB Output is correct
12 Correct 105 ms 89440 KB Output is correct
13 Correct 335 ms 94344 KB Output is correct
14 Correct 151 ms 90444 KB Output is correct
15 Correct 142 ms 90452 KB Output is correct
16 Correct 246 ms 93212 KB Output is correct
17 Correct 305 ms 94292 KB Output is correct
18 Correct 324 ms 95156 KB Output is correct
19 Correct 125 ms 89428 KB Output is correct
20 Correct 107 ms 89440 KB Output is correct
21 Correct 294 ms 94288 KB Output is correct
22 Correct 145 ms 90448 KB Output is correct
23 Correct 140 ms 90376 KB Output is correct
24 Correct 235 ms 93128 KB Output is correct
25 Correct 330 ms 94504 KB Output is correct
26 Correct 293 ms 95080 KB Output is correct
27 Correct 120 ms 89304 KB Output is correct
28 Correct 150 ms 90192 KB Output is correct
29 Correct 350 ms 94488 KB Output is correct
30 Correct 259 ms 92360 KB Output is correct
31 Correct 283 ms 92056 KB Output is correct
32 Correct 377 ms 94492 KB Output is correct
33 Correct 11 ms 85852 KB Output is correct
34 Correct 11 ms 85824 KB Output is correct
35 Correct 12 ms 85852 KB Output is correct
36 Correct 11 ms 85848 KB Output is correct
37 Correct 11 ms 85852 KB Output is correct
38 Correct 11 ms 85948 KB Output is correct
39 Correct 11 ms 85948 KB Output is correct
40 Correct 11 ms 85848 KB Output is correct
41 Correct 11 ms 85848 KB Output is correct
42 Correct 11 ms 85848 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 85852 KB Output is correct
2 Correct 58 ms 86988 KB Output is correct
3 Correct 43 ms 87036 KB Output is correct
4 Correct 81 ms 88912 KB Output is correct
5 Correct 71 ms 89564 KB Output is correct
6 Correct 136 ms 88916 KB Output is correct
7 Correct 47 ms 86876 KB Output is correct
8 Correct 91 ms 88888 KB Output is correct
9 Correct 77 ms 89592 KB Output is correct
10 Correct 82 ms 89548 KB Output is correct
11 Correct 101 ms 87756 KB Output is correct
12 Correct 76 ms 88652 KB Output is correct
13 Correct 85 ms 88012 KB Output is correct
14 Correct 114 ms 88916 KB Output is correct
15 Correct 101 ms 89172 KB Output is correct
16 Correct 11 ms 85852 KB Output is correct
17 Correct 11 ms 85860 KB Output is correct
18 Correct 11 ms 85852 KB Output is correct
19 Correct 12 ms 85868 KB Output is correct
20 Correct 12 ms 85852 KB Output is correct
21 Correct 11 ms 85852 KB Output is correct
22 Correct 11 ms 85852 KB Output is correct
23 Correct 11 ms 85852 KB Output is correct
24 Correct 11 ms 85852 KB Output is correct
25 Correct 11 ms 85848 KB Output is correct