oj.uz

답안 #1051287

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1051287 2024-08-10T03:33:05 Z starr Paths (BOI18_paths) C++17
23 / 100
 494 ms 674384 KB 
#include <bits/stdc++.h>
using namespace std;
// #define int long long

signed 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);
    }
    long long 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 = 0; 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 = 0; mask < (1 << k); mask++){
                ans += dp[i][j][mask];
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 484 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 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 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

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 14928 KB Output is correct
2 Correct 71 ms 5592 KB Output is correct
3 Correct 494 ms 674384 KB Output is correct
4 Correct 135 ms 63188 KB Output is correct
5 Correct 122 ms 54868 KB Output is correct
6 Incorrect 354 ms 451272 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 604 KB Output is correct
3 Correct 0 ms 484 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 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 88 ms 14928 KB Output is correct
12 Correct 71 ms 5592 KB Output is correct
13 Correct 494 ms 674384 KB Output is correct
14 Correct 135 ms 63188 KB Output is correct
15 Correct 122 ms 54868 KB Output is correct
16 Incorrect 354 ms 451272 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 36 ms 2812 KB Output isn't correct
3 Halted 0 ms 0 KB -