답안 #522512

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522512 2022-02-05T05:46:10 Z Leonardo_Paes Paths (BOI18_paths) C++17
100 / 100
323 ms 92684 KB
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5+10, maxl = 1<<5;

int c[maxn];
vector<int> grafo[maxn];

long long dp[maxn][maxl];

long long solve(int u, int mask){
	if(dp[u][mask] != -1) return dp[u][mask];
	long long tot = 1;
	for(int v : grafo[u]) if(!(mask&c[v])) tot += solve(v, mask^c[v]);
	return dp[u][mask] = tot;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, m, k;
	cin >> n >> m >> k;
	for(int i=1; i<=n; i++){
		cin >> c[i];
		c[i] = (1<<(c[i]-1));
	}
	for(int i=1; i<=m; i++){
		int u, v;
		cin >> u >> v;
		grafo[u].push_back(v);
		grafo[v].push_back(u);
	}
	long long ans = 0;
	memset(dp, -1, sizeof dp);
	for(int i=1; i<=n; i++) ans += solve(i, c[i]);
	cout << ans - n << "\n";
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 82456 KB Output is correct
2 Correct 31 ms 82508 KB Output is correct
3 Correct 38 ms 82408 KB Output is correct
4 Correct 36 ms 82440 KB Output is correct
5 Correct 40 ms 82380 KB Output is correct
6 Correct 40 ms 82376 KB Output is correct
7 Correct 32 ms 82372 KB Output is correct
8 Correct 30 ms 82452 KB Output is correct
9 Correct 32 ms 82416 KB Output is correct
10 Correct 33 ms 82428 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 94 ms 86168 KB Output is correct
2 Correct 95 ms 85988 KB Output is correct
3 Correct 274 ms 91972 KB Output is correct
4 Correct 119 ms 87104 KB Output is correct
5 Correct 102 ms 87020 KB Output is correct
6 Correct 270 ms 90308 KB Output is correct
7 Correct 270 ms 92036 KB Output is correct
8 Correct 256 ms 92592 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 82456 KB Output is correct
2 Correct 31 ms 82508 KB Output is correct
3 Correct 38 ms 82408 KB Output is correct
4 Correct 36 ms 82440 KB Output is correct
5 Correct 40 ms 82380 KB Output is correct
6 Correct 40 ms 82376 KB Output is correct
7 Correct 32 ms 82372 KB Output is correct
8 Correct 30 ms 82452 KB Output is correct
9 Correct 32 ms 82416 KB Output is correct
10 Correct 33 ms 82428 KB Output is correct
11 Correct 94 ms 86168 KB Output is correct
12 Correct 95 ms 85988 KB Output is correct
13 Correct 274 ms 91972 KB Output is correct
14 Correct 119 ms 87104 KB Output is correct
15 Correct 102 ms 87020 KB Output is correct
16 Correct 270 ms 90308 KB Output is correct
17 Correct 270 ms 92036 KB Output is correct
18 Correct 256 ms 92592 KB Output is correct
19 Correct 98 ms 86088 KB Output is correct
20 Correct 91 ms 86044 KB Output is correct
21 Correct 266 ms 92024 KB Output is correct
22 Correct 113 ms 86936 KB Output is correct
23 Correct 119 ms 87060 KB Output is correct
24 Correct 276 ms 90372 KB Output is correct
25 Correct 323 ms 92032 KB Output is correct
26 Correct 280 ms 92684 KB Output is correct
27 Correct 103 ms 86108 KB Output is correct
28 Correct 119 ms 86920 KB Output is correct
29 Correct 310 ms 91992 KB Output is correct
30 Correct 279 ms 88808 KB Output is correct
31 Correct 251 ms 89024 KB Output is correct
32 Correct 317 ms 92036 KB Output is correct
33 Correct 41 ms 82456 KB Output is correct
34 Correct 34 ms 82452 KB Output is correct
35 Correct 32 ms 82500 KB Output is correct
36 Correct 31 ms 82436 KB Output is correct
37 Correct 31 ms 82440 KB Output is correct
38 Correct 31 ms 82436 KB Output is correct
39 Correct 31 ms 82452 KB Output is correct
40 Correct 31 ms 82508 KB Output is correct
41 Correct 30 ms 82396 KB Output is correct
42 Correct 39 ms 82388 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 36 ms 82392 KB Output is correct
2 Correct 69 ms 83600 KB Output is correct
3 Correct 49 ms 84304 KB Output is correct
4 Correct 89 ms 86988 KB Output is correct
5 Correct 69 ms 87744 KB Output is correct
6 Correct 123 ms 86992 KB Output is correct
7 Correct 71 ms 84272 KB Output is correct
8 Correct 93 ms 86996 KB Output is correct
9 Correct 73 ms 87712 KB Output is correct
10 Correct 118 ms 87528 KB Output is correct
11 Correct 122 ms 85588 KB Output is correct
12 Correct 81 ms 86812 KB Output is correct
13 Correct 91 ms 85652 KB Output is correct
14 Correct 147 ms 87048 KB Output is correct
15 Correct 98 ms 87104 KB Output is correct
16 Correct 35 ms 82396 KB Output is correct
17 Correct 39 ms 82392 KB Output is correct
18 Correct 32 ms 82480 KB Output is correct
19 Correct 34 ms 82436 KB Output is correct
20 Correct 33 ms 82508 KB Output is correct
21 Correct 33 ms 82412 KB Output is correct
22 Correct 31 ms 82428 KB Output is correct
23 Correct 31 ms 82444 KB Output is correct
24 Correct 32 ms 82456 KB Output is correct
25 Correct 31 ms 82440 KB Output is correct