#include<bits/stdc++.h>
using namespace std;
const int MAXN=300005,LOG=5;
long long dp[MAXN][1<<LOG];
vector<int> adj[MAXN];
int c[MAXN];
long long DP(int now,int mask){
long long &ret=dp[now][mask];
if(ret!=-1)return ret;
ret=1;
for(auto nxt : adj[now]){
if(mask & (1<<c[nxt]))continue;
ret+=DP(nxt,mask+(1<<c[nxt]));
}
return ret;
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n,m,k,u,v;
cin >> n >> m >> k;
for(int i=1;i<=n;i++){
cin >> c[i];
c[i]--;
}
for(int i=1;i<=m;i++){
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(dp,-1,sizeof(dp));
long long ans=-n;
for(int i=1;i<=n;i++){
ans+=DP(i,1<<c[i]);
}
cout << ans << '\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
82540 KB |
Output is correct |
2 |
Correct |
43 ms |
82540 KB |
Output is correct |
3 |
Correct |
43 ms |
82540 KB |
Output is correct |
4 |
Correct |
51 ms |
82540 KB |
Output is correct |
5 |
Correct |
43 ms |
82540 KB |
Output is correct |
6 |
Correct |
46 ms |
82540 KB |
Output is correct |
7 |
Correct |
44 ms |
82540 KB |
Output is correct |
8 |
Correct |
43 ms |
82540 KB |
Output is correct |
9 |
Correct |
44 ms |
82540 KB |
Output is correct |
10 |
Correct |
44 ms |
82540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
125 ms |
89068 KB |
Output is correct |
2 |
Correct |
123 ms |
88348 KB |
Output is correct |
3 |
Correct |
449 ms |
96764 KB |
Output is correct |
4 |
Correct |
191 ms |
90476 KB |
Output is correct |
5 |
Correct |
158 ms |
90476 KB |
Output is correct |
6 |
Correct |
333 ms |
94560 KB |
Output is correct |
7 |
Correct |
535 ms |
96492 KB |
Output is correct |
8 |
Correct |
415 ms |
97388 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
43 ms |
82540 KB |
Output is correct |
2 |
Correct |
43 ms |
82540 KB |
Output is correct |
3 |
Correct |
43 ms |
82540 KB |
Output is correct |
4 |
Correct |
51 ms |
82540 KB |
Output is correct |
5 |
Correct |
43 ms |
82540 KB |
Output is correct |
6 |
Correct |
46 ms |
82540 KB |
Output is correct |
7 |
Correct |
44 ms |
82540 KB |
Output is correct |
8 |
Correct |
43 ms |
82540 KB |
Output is correct |
9 |
Correct |
44 ms |
82540 KB |
Output is correct |
10 |
Correct |
44 ms |
82540 KB |
Output is correct |
11 |
Correct |
125 ms |
89068 KB |
Output is correct |
12 |
Correct |
123 ms |
88348 KB |
Output is correct |
13 |
Correct |
449 ms |
96764 KB |
Output is correct |
14 |
Correct |
191 ms |
90476 KB |
Output is correct |
15 |
Correct |
158 ms |
90476 KB |
Output is correct |
16 |
Correct |
333 ms |
94560 KB |
Output is correct |
17 |
Correct |
535 ms |
96492 KB |
Output is correct |
18 |
Correct |
415 ms |
97388 KB |
Output is correct |
19 |
Correct |
139 ms |
89068 KB |
Output is correct |
20 |
Correct |
117 ms |
88684 KB |
Output is correct |
21 |
Correct |
436 ms |
96620 KB |
Output is correct |
22 |
Correct |
184 ms |
90476 KB |
Output is correct |
23 |
Correct |
159 ms |
90476 KB |
Output is correct |
24 |
Correct |
338 ms |
94560 KB |
Output is correct |
25 |
Correct |
435 ms |
96748 KB |
Output is correct |
26 |
Correct |
426 ms |
97276 KB |
Output is correct |
27 |
Correct |
133 ms |
88428 KB |
Output is correct |
28 |
Correct |
164 ms |
89836 KB |
Output is correct |
29 |
Correct |
524 ms |
96620 KB |
Output is correct |
30 |
Correct |
408 ms |
93024 KB |
Output is correct |
31 |
Correct |
456 ms |
93028 KB |
Output is correct |
32 |
Correct |
523 ms |
96620 KB |
Output is correct |
33 |
Correct |
48 ms |
82540 KB |
Output is correct |
34 |
Correct |
44 ms |
82540 KB |
Output is correct |
35 |
Correct |
44 ms |
82540 KB |
Output is correct |
36 |
Correct |
45 ms |
82540 KB |
Output is correct |
37 |
Correct |
44 ms |
82540 KB |
Output is correct |
38 |
Correct |
44 ms |
82540 KB |
Output is correct |
39 |
Correct |
48 ms |
82540 KB |
Output is correct |
40 |
Correct |
44 ms |
82540 KB |
Output is correct |
41 |
Correct |
44 ms |
82540 KB |
Output is correct |
42 |
Correct |
46 ms |
82540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
46 ms |
82540 KB |
Output is correct |
2 |
Correct |
93 ms |
84552 KB |
Output is correct |
3 |
Correct |
80 ms |
84412 KB |
Output is correct |
4 |
Correct |
146 ms |
87020 KB |
Output is correct |
5 |
Correct |
121 ms |
87780 KB |
Output is correct |
6 |
Correct |
212 ms |
87276 KB |
Output is correct |
7 |
Correct |
71 ms |
84460 KB |
Output is correct |
8 |
Correct |
168 ms |
87148 KB |
Output is correct |
9 |
Correct |
118 ms |
87780 KB |
Output is correct |
10 |
Correct |
144 ms |
87652 KB |
Output is correct |
11 |
Correct |
155 ms |
85736 KB |
Output is correct |
12 |
Correct |
124 ms |
87008 KB |
Output is correct |
13 |
Correct |
162 ms |
85732 KB |
Output is correct |
14 |
Correct |
187 ms |
87020 KB |
Output is correct |
15 |
Correct |
154 ms |
87276 KB |
Output is correct |
16 |
Correct |
42 ms |
82540 KB |
Output is correct |
17 |
Correct |
44 ms |
82668 KB |
Output is correct |
18 |
Correct |
49 ms |
82540 KB |
Output is correct |
19 |
Correct |
42 ms |
82540 KB |
Output is correct |
20 |
Correct |
43 ms |
82540 KB |
Output is correct |
21 |
Correct |
42 ms |
82540 KB |
Output is correct |
22 |
Correct |
43 ms |
82540 KB |
Output is correct |
23 |
Correct |
45 ms |
82540 KB |
Output is correct |
24 |
Correct |
42 ms |
82540 KB |
Output is correct |
25 |
Correct |
42 ms |
82668 KB |
Output is correct |