oj.uz

Submission #1051260

# Submission time Handle Problem Language Result Execution time Memory
1051260 2024-08-10T02:25:25 Z starr Paths (BOI18_paths) C++17
23 / 100
 382 ms 350052 KB 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> col(n);
    for(int i = 0; i < n; i++) cin >> col[i], col[i]--;
    vector<int> adj[n + 5];
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    int dp[k + 5][n + 5][35];
    memset(dp, 0, sizeof dp);
    for(int i = 0; i < n; i++) dp[0][i][(1 << col[i])] = 1;
    for(int i = 1; i < k; i++){
        for(int j = 0; j < n; j++){
            for(int x : adj[j]){
                for(int mask = 1; mask <= (1 << k); mask++){
                    if(!(mask & (1 << col[j]))){
                        dp[i][j][mask | (1 << col[j])] += dp[i - 1][x][mask];
                    }
                }
            }
        }
    }
    // cout << (1 << k) << endl;
    int ans = 0;
    for(int i = 1; i < k; i++){
        for(int j = 0; j < n; j++){
            for(int mask = 1; mask <= (1 << k); mask++){
                ans += dp[i][j][mask];
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 12368 KB Output is correct
2 Correct 76 ms 7072 KB Output is correct
3 Correct 382 ms 350052 KB Output is correct
4 Correct 117 ms 37712 KB Output is correct
5 Correct 119 ms 33532 KB Output is correct
6 Incorrect 264 ms 236092 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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 436 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 85 ms 12368 KB Output is correct
12 Correct 76 ms 7072 KB Output is correct
13 Correct 382 ms 350052 KB Output is correct
14 Correct 117 ms 37712 KB Output is correct
15 Correct 119 ms 33532 KB Output is correct
16 Incorrect 264 ms 236092 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 344 KB Output is correct
2 Incorrect 37 ms 2968 KB Output isn't correct
3 Halted 0 ms 0 KB -