oj.uz

Submission #870657

# Submission time Handle Problem Language Result Execution time Memory
870657 2023-11-08T17:44:41 Z TheSahib Paths (BOI18_paths) C++17
100 / 100
 370 ms 99616 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 19 ms 85852 KB Output is correct
2 Correct 11 ms 85944 KB Output is correct
3 Correct 11 ms 85852 KB Output is correct
4 Correct 11 ms 85980 KB Output is correct
5 Correct 11 ms 85972 KB Output is correct
6 Correct 11 ms 85852 KB Output is correct
7 Correct 12 ms 85852 KB Output is correct
8 Correct 12 ms 85852 KB Output is correct
9 Correct 11 ms 85852 KB Output is correct
10 Correct 11 ms 85848 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 91052 KB Output is correct
2 Correct 108 ms 90708 KB Output is correct
3 Correct 294 ms 98972 KB Output is correct
4 Correct 179 ms 94036 KB Output is correct
5 Correct 170 ms 93696 KB Output is correct
6 Correct 217 ms 97124 KB Output is correct
7 Correct 311 ms 98900 KB Output is correct
8 Correct 304 ms 99616 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 85852 KB Output is correct
2 Correct 11 ms 85944 KB Output is correct
3 Correct 11 ms 85852 KB Output is correct
4 Correct 11 ms 85980 KB Output is correct
5 Correct 11 ms 85972 KB Output is correct
6 Correct 11 ms 85852 KB Output is correct
7 Correct 12 ms 85852 KB Output is correct
8 Correct 12 ms 85852 KB Output is correct
9 Correct 11 ms 85852 KB Output is correct
10 Correct 11 ms 85848 KB Output is correct
11 Correct 127 ms 91052 KB Output is correct
12 Correct 108 ms 90708 KB Output is correct
13 Correct 294 ms 98972 KB Output is correct
14 Correct 179 ms 94036 KB Output is correct
15 Correct 170 ms 93696 KB Output is correct
16 Correct 217 ms 97124 KB Output is correct
17 Correct 311 ms 98900 KB Output is correct
18 Correct 304 ms 99616 KB Output is correct
19 Correct 133 ms 92400 KB Output is correct
20 Correct 110 ms 91684 KB Output is correct
21 Correct 305 ms 98852 KB Output is correct
22 Correct 168 ms 93904 KB Output is correct
23 Correct 160 ms 93696 KB Output is correct
24 Correct 248 ms 97116 KB Output is correct
25 Correct 300 ms 99208 KB Output is correct
26 Correct 289 ms 99524 KB Output is correct
27 Correct 144 ms 91792 KB Output is correct
28 Correct 156 ms 93220 KB Output is correct
29 Correct 334 ms 98964 KB Output is correct
30 Correct 252 ms 95992 KB Output is correct
31 Correct 250 ms 95996 KB Output is correct
32 Correct 370 ms 98968 KB Output is correct
33 Correct 11 ms 86104 KB Output is correct
34 Correct 11 ms 85852 KB Output is correct
35 Correct 12 ms 85848 KB Output is correct
36 Correct 11 ms 85852 KB Output is correct
37 Correct 11 ms 85852 KB Output is correct
38 Correct 12 ms 85852 KB Output is correct
39 Correct 11 ms 85852 KB Output is correct
40 Correct 11 ms 85984 KB Output is correct
41 Correct 11 ms 85976 KB Output is correct
42 Correct 11 ms 85968 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 85936 KB Output is correct
2 Correct 57 ms 87376 KB Output is correct
3 Correct 42 ms 87628 KB Output is correct
4 Correct 81 ms 90196 KB Output is correct
5 Correct 73 ms 90972 KB Output is correct
6 Correct 110 ms 90304 KB Output is correct
7 Correct 48 ms 87632 KB Output is correct
8 Correct 89 ms 90192 KB Output is correct
9 Correct 78 ms 90824 KB Output is correct
10 Correct 93 ms 91088 KB Output is correct
11 Correct 86 ms 88992 KB Output is correct
12 Correct 75 ms 90184 KB Output is correct
13 Correct 83 ms 89292 KB Output is correct
14 Correct 112 ms 90196 KB Output is correct
15 Correct 96 ms 90192 KB Output is correct
16 Correct 11 ms 85848 KB Output is correct
17 Correct 11 ms 85852 KB Output is correct
18 Correct 11 ms 85852 KB Output is correct
19 Correct 11 ms 85852 KB Output is correct
20 Correct 11 ms 85852 KB Output is correct
21 Correct 11 ms 85948 KB Output is correct
22 Correct 11 ms 85852 KB Output is correct
23 Correct 11 ms 85852 KB Output is correct
24 Correct 13 ms 85972 KB Output is correct
25 Correct 11 ms 85852 KB Output is correct