oj.uz

답안 #462615

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
462615 2021-08-11T00:12:38 Z JovanB Paths (BOI18_paths) C++17
100 / 100
 518 ms 97168 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
ll dp[300005][32];
vector <int> graf[300005];
int col[300005];
 
int main(){
    ios_base::sync_with_stdio(false);
    cout.precision(10);
    cout<<fixed;
 
    int n, m, k;
    cin >> n >> m >> k;
    for(int i=1; i<=n; i++){
        cin >> col[i];
        col[i]--;
        dp[i][(1<<col[i])] = 1;
    }
    for(int i=1; i<=m; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    ll res = -n;
    for(int j=0; j<(1<<k); j++){
        for(int i=1; i<=n; i++){
            if(!((1<<col[i]) & j)){
                continue;
            }
            for(auto c : graf[i]){
                dp[i][j] += dp[c][j - (1<<col[i])];
            }
            res += dp[i][j];
        }
    }
    cout << res << "\n";
    return 0;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7392 KB Output is correct
2 Correct 6 ms 7368 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 6 ms 7376 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 6 ms 7356 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 15056 KB Output is correct
2 Correct 100 ms 13356 KB Output is correct
3 Correct 431 ms 96400 KB Output is correct
4 Correct 132 ms 22740 KB Output is correct
5 Correct 153 ms 22724 KB Output is correct
6 Correct 271 ms 69404 KB Output is correct
7 Correct 371 ms 96440 KB Output is correct
8 Correct 355 ms 97168 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 7392 KB Output is correct
2 Correct 6 ms 7368 KB Output is correct
3 Correct 5 ms 7372 KB Output is correct
4 Correct 5 ms 7368 KB Output is correct
5 Correct 5 ms 7372 KB Output is correct
6 Correct 5 ms 7372 KB Output is correct
7 Correct 7 ms 7372 KB Output is correct
8 Correct 6 ms 7376 KB Output is correct
9 Correct 6 ms 7244 KB Output is correct
10 Correct 6 ms 7356 KB Output is correct
11 Correct 114 ms 15056 KB Output is correct
12 Correct 100 ms 13356 KB Output is correct
13 Correct 431 ms 96400 KB Output is correct
14 Correct 132 ms 22740 KB Output is correct
15 Correct 153 ms 22724 KB Output is correct
16 Correct 271 ms 69404 KB Output is correct
17 Correct 371 ms 96440 KB Output is correct
18 Correct 355 ms 97168 KB Output is correct
19 Correct 90 ms 15064 KB Output is correct
20 Correct 86 ms 13420 KB Output is correct
21 Correct 395 ms 96516 KB Output is correct
22 Correct 132 ms 22748 KB Output is correct
23 Correct 178 ms 22704 KB Output is correct
24 Correct 315 ms 69360 KB Output is correct
25 Correct 409 ms 96504 KB Output is correct
26 Correct 410 ms 97120 KB Output is correct
27 Correct 74 ms 13356 KB Output is correct
28 Correct 140 ms 16556 KB Output is correct
29 Correct 499 ms 96516 KB Output is correct
30 Correct 343 ms 55264 KB Output is correct
31 Correct 411 ms 55344 KB Output is correct
32 Correct 518 ms 96476 KB Output is correct
33 Correct 6 ms 7372 KB Output is correct
34 Correct 6 ms 7372 KB Output is correct
35 Correct 6 ms 7372 KB Output is correct
36 Correct 6 ms 7372 KB Output is correct
37 Correct 5 ms 7372 KB Output is correct
38 Correct 6 ms 7352 KB Output is correct
39 Correct 8 ms 7372 KB Output is correct
40 Correct 5 ms 7372 KB Output is correct
41 Correct 4 ms 7372 KB Output is correct
42 Correct 5 ms 7288 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 7308 KB Output is correct
2 Correct 38 ms 9312 KB Output is correct
3 Correct 30 ms 9328 KB Output is correct
4 Correct 96 ms 36936 KB Output is correct
5 Correct 82 ms 37588 KB Output is correct
6 Correct 207 ms 36932 KB Output is correct
7 Correct 30 ms 9464 KB Output is correct
8 Correct 132 ms 36936 KB Output is correct
9 Correct 95 ms 37644 KB Output is correct
10 Correct 122 ms 37696 KB Output is correct
11 Correct 102 ms 23032 KB Output is correct
12 Correct 108 ms 30496 KB Output is correct
13 Correct 107 ms 23244 KB Output is correct
14 Correct 194 ms 36904 KB Output is correct
15 Correct 210 ms 37108 KB Output is correct
16 Correct 5 ms 7372 KB Output is correct
17 Correct 6 ms 7372 KB Output is correct
18 Correct 6 ms 7376 KB Output is correct
19 Correct 6 ms 7372 KB Output is correct
20 Correct 5 ms 7372 KB Output is correct
21 Correct 5 ms 7372 KB Output is correct
22 Correct 5 ms 7372 KB Output is correct
23 Correct 6 ms 7372 KB Output is correct
24 Correct 5 ms 7368 KB Output is correct
25 Correct 5 ms 7372 KB Output is correct