답안 #160283

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
160283 2019-10-26T18:02:14 Z pamaj Paths (BOI18_paths) C++14
100 / 100
563 ms 173560 KB
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
int n, m, k;
int cor[maxn];
int dp[maxn][129];
bool vis[maxn];
 
vector<int> G[maxn];
 
 
inline ll dfs(int x, int mask)
{
	//if(mask == (1 << (k + 1)) - 1) return 1;
	
	if(dp[x][mask] != -1) return dp[x][mask];
	
	ll cont = 0;
	
	for(auto u : G[x])
	{	
		if((mask & (1 << cor[u])) == 0) 
		{
			cont += 1 + dfs(u, (mask | (1 << cor[u])));
		}
 
		//cont += dfs(u, (1 << cor[u]));
	}
 
	return dp[x][mask] = cont;
 
}
 
int main()
{
	ios::sync_with_stdio(false), cin.tie(nullptr);
	
	cin >> n >> m >> k;
 
	for(int i = 1; i <= n; i++)
		cin >> cor[i];
 
	for(int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	memset(dp, -1, sizeof(dp));
 
	ll ans = 0;
	for(int i = 1; i <= n; i++)
	{	
		ans += dfs(i, 1 << cor[i]);
	}
	cout << ans << "\n";
 
}
# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 159036 KB Output is correct
2 Correct 209 ms 158968 KB Output is correct
3 Correct 143 ms 158940 KB Output is correct
4 Correct 140 ms 158832 KB Output is correct
5 Correct 143 ms 158852 KB Output is correct
6 Correct 142 ms 158904 KB Output is correct
7 Correct 141 ms 158840 KB Output is correct
8 Correct 138 ms 158812 KB Output is correct
9 Correct 149 ms 158908 KB Output is correct
10 Correct 140 ms 158872 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 240 ms 165368 KB Output is correct
2 Correct 223 ms 164724 KB Output is correct
3 Correct 509 ms 173032 KB Output is correct
4 Correct 282 ms 166800 KB Output is correct
5 Correct 307 ms 166984 KB Output is correct
6 Correct 514 ms 170868 KB Output is correct
7 Correct 503 ms 173052 KB Output is correct
8 Correct 498 ms 173556 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 159036 KB Output is correct
2 Correct 209 ms 158968 KB Output is correct
3 Correct 143 ms 158940 KB Output is correct
4 Correct 140 ms 158832 KB Output is correct
5 Correct 143 ms 158852 KB Output is correct
6 Correct 142 ms 158904 KB Output is correct
7 Correct 141 ms 158840 KB Output is correct
8 Correct 138 ms 158812 KB Output is correct
9 Correct 149 ms 158908 KB Output is correct
10 Correct 140 ms 158872 KB Output is correct
11 Correct 240 ms 165368 KB Output is correct
12 Correct 223 ms 164724 KB Output is correct
13 Correct 509 ms 173032 KB Output is correct
14 Correct 282 ms 166800 KB Output is correct
15 Correct 307 ms 166984 KB Output is correct
16 Correct 514 ms 170868 KB Output is correct
17 Correct 503 ms 173052 KB Output is correct
18 Correct 498 ms 173556 KB Output is correct
19 Correct 240 ms 165340 KB Output is correct
20 Correct 218 ms 164748 KB Output is correct
21 Correct 507 ms 173048 KB Output is correct
22 Correct 318 ms 166848 KB Output is correct
23 Correct 253 ms 166932 KB Output is correct
24 Correct 402 ms 170860 KB Output is correct
25 Correct 498 ms 172968 KB Output is correct
26 Correct 484 ms 173560 KB Output is correct
27 Correct 241 ms 164772 KB Output is correct
28 Correct 263 ms 166152 KB Output is correct
29 Correct 563 ms 173044 KB Output is correct
30 Correct 469 ms 169324 KB Output is correct
31 Correct 495 ms 169364 KB Output is correct
32 Correct 559 ms 173048 KB Output is correct
33 Correct 132 ms 158940 KB Output is correct
34 Correct 136 ms 158840 KB Output is correct
35 Correct 133 ms 158944 KB Output is correct
36 Correct 136 ms 158824 KB Output is correct
37 Correct 134 ms 158916 KB Output is correct
38 Correct 147 ms 158812 KB Output is correct
39 Correct 134 ms 158828 KB Output is correct
40 Correct 154 ms 158896 KB Output is correct
41 Correct 136 ms 158936 KB Output is correct
42 Correct 143 ms 158800 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 137 ms 158840 KB Output is correct
2 Correct 187 ms 160624 KB Output is correct
3 Correct 170 ms 160748 KB Output is correct
4 Correct 227 ms 163464 KB Output is correct
5 Correct 205 ms 164208 KB Output is correct
6 Correct 250 ms 163420 KB Output is correct
7 Correct 173 ms 160888 KB Output is correct
8 Correct 232 ms 163460 KB Output is correct
9 Correct 202 ms 164184 KB Output is correct
10 Correct 228 ms 164024 KB Output is correct
11 Correct 236 ms 162036 KB Output is correct
12 Correct 209 ms 163184 KB Output is correct
13 Correct 222 ms 162296 KB Output is correct
14 Correct 255 ms 163448 KB Output is correct
15 Correct 235 ms 163544 KB Output is correct
16 Correct 134 ms 158792 KB Output is correct
17 Correct 137 ms 158808 KB Output is correct
18 Correct 135 ms 158940 KB Output is correct
19 Correct 140 ms 158888 KB Output is correct
20 Correct 139 ms 158816 KB Output is correct
21 Correct 138 ms 158840 KB Output is correct
22 Correct 134 ms 158856 KB Output is correct
23 Correct 136 ms 158840 KB Output is correct
24 Correct 134 ms 158840 KB Output is correct
25 Correct 133 ms 158840 KB Output is correct