답안 #413827

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
413827 2021-05-29T14:50:40 Z ak2006 Paths (BOI18_paths) C++14
100 / 100
668 ms 130244 KB
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vc = vector<char>;
using vvc = vector<vc>;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
void setIO()
{
	fast;
}
int n = 3e5 + 5,m = 3e5 + 5,k = 5;
vvi adj(n);
vi col(n);
vvl dp(n,vl(1<<k));
vvb vis(n,vb(1<<k));
void dfs(int u,int mask)
{
	int mask2 = mask |  (1<<col[u]);
	dp[u][mask] = 1;
	vis[u][mask] = 1;
	for (int v:adj[u]){
		if ((mask2 & (1<<col[v])))continue;
		if (!vis[v][mask2])dfs(v,mask2);
		dp[u][mask] += dp[v][mask2];
	}
}
int main()
{
	setIO();
	cin>>n>>m>>k;
	for (int i = 1;i<=n;i++){cin>>col[i];col[i]--;}
	while (m--){
		int u,v;
		cin>>u>>v;
		adj[u].pb(v),adj[v].pb(u);
	}
	ll ans = 0;
	for (int i = 1;i<=n;i++){
		for (int mask = 0;mask < (1<<k);mask++){
			if (mask & (1<<col[i]))continue;
			dfs(i,mask);
			if (mask == 0)ans += dp[i][0] - 1;
		}
	}
	cout<<ans;
	return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 116552 KB Output is correct
2 Correct 127 ms 116540 KB Output is correct
3 Correct 116 ms 116460 KB Output is correct
4 Correct 119 ms 116552 KB Output is correct
5 Correct 116 ms 116488 KB Output is correct
6 Correct 113 ms 116452 KB Output is correct
7 Correct 119 ms 116636 KB Output is correct
8 Correct 115 ms 116496 KB Output is correct
9 Correct 116 ms 116616 KB Output is correct
10 Correct 114 ms 116500 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 120208 KB Output is correct
2 Correct 200 ms 122308 KB Output is correct
3 Correct 537 ms 129404 KB Output is correct
4 Correct 263 ms 124268 KB Output is correct
5 Correct 216 ms 124212 KB Output is correct
6 Correct 449 ms 127760 KB Output is correct
7 Correct 523 ms 129400 KB Output is correct
8 Correct 514 ms 130228 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 117 ms 116552 KB Output is correct
2 Correct 127 ms 116540 KB Output is correct
3 Correct 116 ms 116460 KB Output is correct
4 Correct 119 ms 116552 KB Output is correct
5 Correct 116 ms 116488 KB Output is correct
6 Correct 113 ms 116452 KB Output is correct
7 Correct 119 ms 116636 KB Output is correct
8 Correct 115 ms 116496 KB Output is correct
9 Correct 116 ms 116616 KB Output is correct
10 Correct 114 ms 116500 KB Output is correct
11 Correct 211 ms 120208 KB Output is correct
12 Correct 200 ms 122308 KB Output is correct
13 Correct 537 ms 129404 KB Output is correct
14 Correct 263 ms 124268 KB Output is correct
15 Correct 216 ms 124212 KB Output is correct
16 Correct 449 ms 127760 KB Output is correct
17 Correct 523 ms 129400 KB Output is correct
18 Correct 514 ms 130228 KB Output is correct
19 Correct 216 ms 122928 KB Output is correct
20 Correct 203 ms 122416 KB Output is correct
21 Correct 537 ms 129408 KB Output is correct
22 Correct 244 ms 124284 KB Output is correct
23 Correct 223 ms 124292 KB Output is correct
24 Correct 442 ms 127756 KB Output is correct
25 Correct 549 ms 129480 KB Output is correct
26 Correct 527 ms 130244 KB Output is correct
27 Correct 238 ms 122304 KB Output is correct
28 Correct 274 ms 123792 KB Output is correct
29 Correct 668 ms 129396 KB Output is correct
30 Correct 585 ms 126420 KB Output is correct
31 Correct 589 ms 126352 KB Output is correct
32 Correct 653 ms 129412 KB Output is correct
33 Correct 119 ms 116512 KB Output is correct
34 Correct 137 ms 116548 KB Output is correct
35 Correct 118 ms 116520 KB Output is correct
36 Correct 118 ms 116548 KB Output is correct
37 Correct 117 ms 116496 KB Output is correct
38 Correct 118 ms 116552 KB Output is correct
39 Correct 124 ms 116484 KB Output is correct
40 Correct 118 ms 116464 KB Output is correct
41 Correct 119 ms 116456 KB Output is correct
42 Correct 118 ms 116488 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 132 ms 116464 KB Output is correct
2 Correct 177 ms 117624 KB Output is correct
3 Correct 143 ms 118340 KB Output is correct
4 Correct 220 ms 120824 KB Output is correct
5 Correct 208 ms 121356 KB Output is correct
6 Correct 302 ms 120572 KB Output is correct
7 Correct 155 ms 118296 KB Output is correct
8 Correct 248 ms 120660 KB Output is correct
9 Correct 257 ms 121412 KB Output is correct
10 Correct 277 ms 121496 KB Output is correct
11 Correct 343 ms 119392 KB Output is correct
12 Correct 311 ms 120680 KB Output is correct
13 Correct 323 ms 119692 KB Output is correct
14 Correct 317 ms 120688 KB Output is correct
15 Correct 291 ms 120788 KB Output is correct
16 Correct 119 ms 116532 KB Output is correct
17 Correct 122 ms 116524 KB Output is correct
18 Correct 125 ms 116620 KB Output is correct
19 Correct 119 ms 116496 KB Output is correct
20 Correct 121 ms 116548 KB Output is correct
21 Correct 120 ms 116480 KB Output is correct
22 Correct 143 ms 116496 KB Output is correct
23 Correct 129 ms 116548 KB Output is correct
24 Correct 118 ms 116528 KB Output is correct
25 Correct 117 ms 116548 KB Output is correct