Submission #413827

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
413827	2021-05-29T14:50:40 Z	ak2006	Paths (BOI18_paths)	C++14	100 / 100	668 ms	130244 KB

paths

#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;
}

Subtask #1

23.0 / 23.0

#	Verdict	Execution time	Memory	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

Subtask #2

20.0 / 20.0

#	Verdict	Execution time	Memory	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

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	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

Subtask #4

30.0 / 30.0

#	Verdict	Execution time	Memory	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