oj.uz

답안 #314414

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
314414 2020-10-19T20:12:23 Z Temmie Paths (BOI18_paths) C++17
100 / 100
 1028 ms 109176 KB 
#include <bits/stdc++.h>

typedef long long ll;

int cnt(int x) {
	int r = 0;
	while (x) {
		r += x & 1;
		x >>= 1;
	}
	return r;
}

int main() {
	std::ios::sync_with_stdio(0); std::cin.tie(0);
	
	int n, m, k; std::cin >> n >> m >> k;
	std::vector <int> col(n);
	std::vector <std::vector <ll>> dp(3e5 + 5, std::vector <ll> (32, 0));
	for (int i = 0; i < n; i++) {
		std::cin >> col[i]; col[i]--;
		dp[i][1 << col[i]] = 1;
	}
	std::vector <std::vector <int>> g(n);
	for (int i = 0; i < m; i++) {
		int u, v; std::cin >> u >> v; u--, v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for (int i = 1; i < k; i++)
		for (int j = 0; j < n; j++)
			for (int l = 1; l < 32; l++) {
				if (cnt(l) != i) continue;
				for (int x : g[j])
					if (!(l & (1 << col[x])))
						dp[x][(l ^ (1 << col[x]))] += dp[j][l];
			}
	ll ans = -n;
	for (int i = 0; i < n; i++)
		for (int j = 1; j < 32; j++)
			ans += dp[i][j];
	std::cout << ans << "\n";
	
}

Subtask #1
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 87288 KB Output is correct
2 Correct 67 ms 87288 KB Output is correct
3 Correct 66 ms 87160 KB Output is correct
4 Correct 66 ms 87288 KB Output is correct
5 Correct 65 ms 87160 KB Output is correct
6 Correct 67 ms 87288 KB Output is correct
7 Correct 65 ms 87288 KB Output is correct
8 Correct 67 ms 87288 KB Output is correct
9 Correct 65 ms 87160 KB Output is correct
10 Correct 66 ms 87288 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 93816 KB Output is correct
2 Correct 206 ms 93176 KB Output is correct
3 Correct 761 ms 108664 KB Output is correct
4 Correct 212 ms 95864 KB Output is correct
5 Correct 160 ms 95992 KB Output is correct
6 Correct 681 ms 104020 KB Output is correct
7 Correct 754 ms 108364 KB Output is correct
8 Correct 763 ms 109176 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 87288 KB Output is correct
2 Correct 67 ms 87288 KB Output is correct
3 Correct 66 ms 87160 KB Output is correct
4 Correct 66 ms 87288 KB Output is correct
5 Correct 65 ms 87160 KB Output is correct
6 Correct 67 ms 87288 KB Output is correct
7 Correct 65 ms 87288 KB Output is correct
8 Correct 67 ms 87288 KB Output is correct
9 Correct 65 ms 87160 KB Output is correct
10 Correct 66 ms 87288 KB Output is correct
11 Correct 234 ms 93816 KB Output is correct
12 Correct 206 ms 93176 KB Output is correct
13 Correct 761 ms 108664 KB Output is correct
14 Correct 212 ms 95864 KB Output is correct
15 Correct 160 ms 95992 KB Output is correct
16 Correct 681 ms 104020 KB Output is correct
17 Correct 754 ms 108364 KB Output is correct
18 Correct 763 ms 109176 KB Output is correct
19 Correct 240 ms 93944 KB Output is correct
20 Correct 205 ms 93132 KB Output is correct
21 Correct 754 ms 108488 KB Output is correct
22 Correct 218 ms 95864 KB Output is correct
23 Correct 162 ms 95864 KB Output is correct
24 Correct 669 ms 103916 KB Output is correct
25 Correct 762 ms 108408 KB Output is correct
26 Correct 765 ms 109056 KB Output is correct
27 Correct 258 ms 93180 KB Output is correct
28 Correct 306 ms 94712 KB Output is correct
29 Correct 1028 ms 108408 KB Output is correct
30 Correct 765 ms 101228 KB Output is correct
31 Correct 797 ms 101232 KB Output is correct
32 Correct 1022 ms 108404 KB Output is correct
33 Correct 65 ms 87288 KB Output is correct
34 Correct 66 ms 87288 KB Output is correct
35 Correct 65 ms 87260 KB Output is correct
36 Correct 66 ms 87160 KB Output is correct
37 Correct 66 ms 87160 KB Output is correct
38 Correct 67 ms 87284 KB Output is correct
39 Correct 65 ms 87288 KB Output is correct
40 Correct 66 ms 87288 KB Output is correct
41 Correct 66 ms 87288 KB Output is correct
42 Correct 66 ms 87160 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 65 ms 87160 KB Output is correct
2 Correct 135 ms 89080 KB Output is correct
3 Correct 112 ms 89084 KB Output is correct
4 Correct 255 ms 94076 KB Output is correct
5 Correct 232 ms 94832 KB Output is correct
6 Correct 402 ms 94328 KB Output is correct
7 Correct 129 ms 89080 KB Output is correct
8 Correct 338 ms 94328 KB Output is correct
9 Correct 276 ms 94832 KB Output is correct
10 Correct 316 ms 94964 KB Output is correct
11 Correct 249 ms 91508 KB Output is correct
12 Correct 276 ms 93424 KB Output is correct
13 Correct 254 ms 91900 KB Output is correct
14 Correct 401 ms 94200 KB Output is correct
15 Correct 403 ms 94328 KB Output is correct
16 Correct 65 ms 87160 KB Output is correct
17 Correct 66 ms 87160 KB Output is correct
18 Correct 71 ms 87232 KB Output is correct
19 Correct 66 ms 87288 KB Output is correct
20 Correct 65 ms 87160 KB Output is correct
21 Correct 66 ms 87268 KB Output is correct
22 Correct 65 ms 87288 KB Output is correct
23 Correct 66 ms 87288 KB Output is correct
24 Correct 67 ms 87160 KB Output is correct
25 Correct 65 ms 87288 KB Output is correct