oj.uz

답안 #94326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
94326 2019-01-17T17:56:32 Z dalgerok Paths (BOI18_paths) C++14
100 / 100
 520 ms 99576 KB 
#include<bits/stdc++.h>
using namespace std;


const int N = 3e5 + 5, M = (1 << 5) + 1;




int n, m, k, a[N];
vector < int > g[N];
long long dp[M][N];

long long rec(int mask, int v){
    if(dp[mask][v] != -1){
        return dp[mask][v];
    }
    dp[mask][v] = 1;
    for(int to : g[v]){
        if(!((mask >> a[to]) & 1)){
            dp[mask][v] += rec((mask | (1 << a[to])), to);
        }
    }
    return dp[mask][v];
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] -= 1;
    }
    for(int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    long long ans = 0;
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i++){
        ans += rec((1 << a[i]), i);
    }
    cout << ans - n;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 84988 KB Output is correct
2 Correct 60 ms 84856 KB Output is correct
3 Correct 61 ms 84856 KB Output is correct
4 Correct 60 ms 85036 KB Output is correct
5 Correct 59 ms 84856 KB Output is correct
6 Correct 60 ms 84856 KB Output is correct
7 Correct 70 ms 84856 KB Output is correct
8 Correct 59 ms 84856 KB Output is correct
9 Correct 95 ms 84856 KB Output is correct
10 Correct 60 ms 84796 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 140 ms 91384 KB Output is correct
2 Correct 129 ms 90620 KB Output is correct
3 Correct 466 ms 98808 KB Output is correct
4 Correct 204 ms 92792 KB Output is correct
5 Correct 181 ms 92872 KB Output is correct
6 Correct 315 ms 96872 KB Output is correct
7 Correct 335 ms 98808 KB Output is correct
8 Correct 353 ms 99568 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 84988 KB Output is correct
2 Correct 60 ms 84856 KB Output is correct
3 Correct 61 ms 84856 KB Output is correct
4 Correct 60 ms 85036 KB Output is correct
5 Correct 59 ms 84856 KB Output is correct
6 Correct 60 ms 84856 KB Output is correct
7 Correct 70 ms 84856 KB Output is correct
8 Correct 59 ms 84856 KB Output is correct
9 Correct 95 ms 84856 KB Output is correct
10 Correct 60 ms 84796 KB Output is correct
11 Correct 140 ms 91384 KB Output is correct
12 Correct 129 ms 90620 KB Output is correct
13 Correct 466 ms 98808 KB Output is correct
14 Correct 204 ms 92792 KB Output is correct
15 Correct 181 ms 92872 KB Output is correct
16 Correct 315 ms 96872 KB Output is correct
17 Correct 335 ms 98808 KB Output is correct
18 Correct 353 ms 99568 KB Output is correct
19 Correct 138 ms 91328 KB Output is correct
20 Correct 118 ms 90688 KB Output is correct
21 Correct 340 ms 99036 KB Output is correct
22 Correct 188 ms 92940 KB Output is correct
23 Correct 179 ms 92792 KB Output is correct
24 Correct 307 ms 96980 KB Output is correct
25 Correct 426 ms 98936 KB Output is correct
26 Correct 472 ms 99576 KB Output is correct
27 Correct 147 ms 90616 KB Output is correct
28 Correct 179 ms 92148 KB Output is correct
29 Correct 520 ms 98808 KB Output is correct
30 Correct 410 ms 95336 KB Output is correct
31 Correct 381 ms 95344 KB Output is correct
32 Correct 471 ms 98936 KB Output is correct
33 Correct 69 ms 84856 KB Output is correct
34 Correct 69 ms 84856 KB Output is correct
35 Correct 69 ms 84856 KB Output is correct
36 Correct 69 ms 84900 KB Output is correct
37 Correct 71 ms 84856 KB Output is correct
38 Correct 70 ms 84892 KB Output is correct
39 Correct 69 ms 84856 KB Output is correct
40 Correct 68 ms 84856 KB Output is correct
41 Correct 69 ms 84856 KB Output is correct
42 Correct 68 ms 84856 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 84856 KB Output is correct
2 Correct 93 ms 86648 KB Output is correct
3 Correct 80 ms 86648 KB Output is correct
4 Correct 124 ms 89324 KB Output is correct
5 Correct 106 ms 90160 KB Output is correct
6 Correct 166 ms 89564 KB Output is correct
7 Correct 95 ms 86724 KB Output is correct
8 Correct 136 ms 89464 KB Output is correct
9 Correct 129 ms 90212 KB Output is correct
10 Correct 146 ms 90004 KB Output is correct
11 Correct 153 ms 88008 KB Output is correct
12 Correct 116 ms 89304 KB Output is correct
13 Correct 138 ms 88216 KB Output is correct
14 Correct 168 ms 89432 KB Output is correct
15 Correct 167 ms 89424 KB Output is correct
16 Correct 68 ms 84856 KB Output is correct
17 Correct 69 ms 85032 KB Output is correct
18 Correct 68 ms 84984 KB Output is correct
19 Correct 68 ms 84856 KB Output is correct
20 Correct 69 ms 84856 KB Output is correct
21 Correct 70 ms 84856 KB Output is correct
22 Correct 71 ms 84856 KB Output is correct
23 Correct 68 ms 84856 KB Output is correct
24 Correct 69 ms 84984 KB Output is correct
25 Correct 68 ms 84856 KB Output is correct