oj.uz

답안 #162983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162983 2019-11-10T15:32:08 Z Minnakhmetov Paths (BOI18_paths) C++14
100 / 100
 793 ms 322072 KB 
#include <bits/stdc++.h>
    
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
 
using namespace std;

const int N = 3e5 + 5, K = 5;
int a[N];
vector<int> g[N];
ll dp[K][N][1 << K];
 
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++) {
    	cin >> a[i];
    	a[i]--;
    	dp[0][i][1 << a[i]] = 1;
    }

    for (int i = 0; i < m; i++) {
    	int x, y;
    	cin >> x >> y;
    	x--, y--;
    	g[x].push_back(y);
    	g[y].push_back(x);
    }

    for (int i = 1; i < k; i++) {
    	for (int j = 0; j < n; j++) {
    		for (int to : g[j]) {
    			int h = (1 << k) - 1 - (1 << a[j]);
    			for (int z = h; z != 0; z = (z - 1) & h) {
    				dp[i][j][z | (1 << a[j])] += dp[i - 1][to][z];
    			}
    		}
    	}
    }

    ll ans = 0;
    for (int i = 1; i < k; i++) {
    	for (int j = 0; j < n; j++) {
    		for (int z = 0; z < (1 << k); z++) {
    			ans += dp[i][j][z];
    		}
    	}
    }

    cout << ans;

    return 0;
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7388 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 8 ms 7544 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 113 ms 17636 KB Output is correct
2 Correct 84 ms 13816 KB Output is correct
3 Correct 569 ms 246920 KB Output is correct
4 Correct 170 ms 30428 KB Output is correct
5 Correct 140 ms 22768 KB Output is correct
6 Correct 406 ms 169744 KB Output is correct
7 Correct 567 ms 247044 KB Output is correct
8 Correct 589 ms 247544 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7544 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 9 ms 7388 KB Output is correct
6 Correct 9 ms 7544 KB Output is correct
7 Correct 9 ms 7416 KB Output is correct
8 Correct 8 ms 7544 KB Output is correct
9 Correct 8 ms 7416 KB Output is correct
10 Correct 8 ms 7416 KB Output is correct
11 Correct 113 ms 17636 KB Output is correct
12 Correct 84 ms 13816 KB Output is correct
13 Correct 569 ms 246920 KB Output is correct
14 Correct 170 ms 30428 KB Output is correct
15 Correct 140 ms 22768 KB Output is correct
16 Correct 406 ms 169744 KB Output is correct
17 Correct 567 ms 247044 KB Output is correct
18 Correct 589 ms 247544 KB Output is correct
19 Correct 116 ms 17644 KB Output is correct
20 Correct 85 ms 13820 KB Output is correct
21 Correct 596 ms 247144 KB Output is correct
22 Correct 164 ms 30328 KB Output is correct
23 Correct 150 ms 22960 KB Output is correct
24 Correct 414 ms 169704 KB Output is correct
25 Correct 589 ms 246904 KB Output is correct
26 Correct 599 ms 247496 KB Output is correct
27 Correct 100 ms 13944 KB Output is correct
28 Correct 151 ms 22648 KB Output is correct
29 Correct 793 ms 322072 KB Output is correct
30 Correct 543 ms 168452 KB Output is correct
31 Correct 535 ms 168336 KB Output is correct
32 Correct 775 ms 322040 KB Output is correct
33 Correct 9 ms 7420 KB Output is correct
34 Correct 9 ms 7544 KB Output is correct
35 Correct 9 ms 7416 KB Output is correct
36 Correct 9 ms 7420 KB Output is correct
37 Correct 8 ms 7416 KB Output is correct
38 Correct 8 ms 7544 KB Output is correct
39 Correct 9 ms 7544 KB Output is correct
40 Correct 9 ms 7544 KB Output is correct
41 Correct 9 ms 7416 KB Output is correct
42 Correct 9 ms 7416 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 50 ms 9976 KB Output is correct
3 Correct 32 ms 9592 KB Output is correct
4 Correct 164 ms 87132 KB Output is correct
5 Correct 147 ms 87892 KB Output is correct
6 Correct 371 ms 137296 KB Output is correct
7 Correct 37 ms 9716 KB Output is correct
8 Correct 248 ms 112300 KB Output is correct
9 Correct 198 ms 112876 KB Output is correct
10 Correct 220 ms 112760 KB Output is correct
11 Correct 200 ms 73332 KB Output is correct
12 Correct 242 ms 105712 KB Output is correct
13 Correct 202 ms 73328 KB Output is correct
14 Correct 377 ms 137336 KB Output is correct
15 Correct 496 ms 137464 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7544 KB Output is correct
18 Correct 9 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct
20 Correct 9 ms 7416 KB Output is correct
21 Correct 9 ms 7544 KB Output is correct
22 Correct 9 ms 7548 KB Output is correct
23 Correct 9 ms 7544 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 9 ms 7416 KB Output is correct