# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
464006 |
2021-08-12T07:23:32 Z |
bonopo |
Paths (BOI18_paths) |
C++14 |
|
591 ms |
97108 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second
typedef long long ll;
const int MM=3e5+5, MOD=1e9+7, LOG=19;
int N, M, K, c[MM]; ll dp[32][MM], ans;
vector<int> adj[MM];
ll dfs(int u, int mask) {
if((mask&(1<<c[u]))==0) return 0;
ll &ret=dp[mask][u];
if(~ret) return ret;
ret=0;
for(int &v:adj[u]) if(mask&(1<<c[v])) ret+=+dfs(v, mask^(1<<c[u]));
return ret;
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin>>N>>M>>K;
memset(dp, -1, sizeof(dp));
for(int i=1; i<=N; ++i) cin>>c[i], --c[i], dp[1<<c[i]][i]=1;
for(int i=1, u, v; i<=M; ++i) {
cin>>u>>v;
adj[u].pb(v); adj[v].pb(u); }
for(int i=1; i<=N; ++i) for(int k=0; k<(1<<K); ++k) ans+=dfs(i, k);
cout<<ans-N<<el;
}
// MM
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
82476 KB |
Output is correct |
2 |
Correct |
36 ms |
82508 KB |
Output is correct |
3 |
Correct |
36 ms |
82408 KB |
Output is correct |
4 |
Correct |
35 ms |
82496 KB |
Output is correct |
5 |
Correct |
37 ms |
82460 KB |
Output is correct |
6 |
Correct |
36 ms |
82500 KB |
Output is correct |
7 |
Correct |
37 ms |
82444 KB |
Output is correct |
8 |
Correct |
36 ms |
82508 KB |
Output is correct |
9 |
Correct |
35 ms |
82520 KB |
Output is correct |
10 |
Correct |
35 ms |
82372 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
129 ms |
88900 KB |
Output is correct |
2 |
Correct |
119 ms |
88324 KB |
Output is correct |
3 |
Correct |
421 ms |
96436 KB |
Output is correct |
4 |
Correct |
187 ms |
90328 KB |
Output is correct |
5 |
Correct |
156 ms |
90352 KB |
Output is correct |
6 |
Correct |
294 ms |
94408 KB |
Output is correct |
7 |
Correct |
391 ms |
96456 KB |
Output is correct |
8 |
Correct |
403 ms |
97092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
82476 KB |
Output is correct |
2 |
Correct |
36 ms |
82508 KB |
Output is correct |
3 |
Correct |
36 ms |
82408 KB |
Output is correct |
4 |
Correct |
35 ms |
82496 KB |
Output is correct |
5 |
Correct |
37 ms |
82460 KB |
Output is correct |
6 |
Correct |
36 ms |
82500 KB |
Output is correct |
7 |
Correct |
37 ms |
82444 KB |
Output is correct |
8 |
Correct |
36 ms |
82508 KB |
Output is correct |
9 |
Correct |
35 ms |
82520 KB |
Output is correct |
10 |
Correct |
35 ms |
82372 KB |
Output is correct |
11 |
Correct |
129 ms |
88900 KB |
Output is correct |
12 |
Correct |
119 ms |
88324 KB |
Output is correct |
13 |
Correct |
421 ms |
96436 KB |
Output is correct |
14 |
Correct |
187 ms |
90328 KB |
Output is correct |
15 |
Correct |
156 ms |
90352 KB |
Output is correct |
16 |
Correct |
294 ms |
94408 KB |
Output is correct |
17 |
Correct |
391 ms |
96456 KB |
Output is correct |
18 |
Correct |
403 ms |
97092 KB |
Output is correct |
19 |
Correct |
144 ms |
88900 KB |
Output is correct |
20 |
Correct |
120 ms |
88356 KB |
Output is correct |
21 |
Correct |
421 ms |
96500 KB |
Output is correct |
22 |
Correct |
151 ms |
90308 KB |
Output is correct |
23 |
Correct |
137 ms |
90408 KB |
Output is correct |
24 |
Correct |
305 ms |
94440 KB |
Output is correct |
25 |
Correct |
412 ms |
96496 KB |
Output is correct |
26 |
Correct |
398 ms |
97108 KB |
Output is correct |
27 |
Correct |
146 ms |
88268 KB |
Output is correct |
28 |
Correct |
173 ms |
89780 KB |
Output is correct |
29 |
Correct |
591 ms |
96472 KB |
Output is correct |
30 |
Correct |
415 ms |
92920 KB |
Output is correct |
31 |
Correct |
395 ms |
92860 KB |
Output is correct |
32 |
Correct |
577 ms |
96504 KB |
Output is correct |
33 |
Correct |
39 ms |
82372 KB |
Output is correct |
34 |
Correct |
40 ms |
82384 KB |
Output is correct |
35 |
Correct |
37 ms |
82480 KB |
Output is correct |
36 |
Correct |
38 ms |
82500 KB |
Output is correct |
37 |
Correct |
38 ms |
82532 KB |
Output is correct |
38 |
Correct |
39 ms |
82388 KB |
Output is correct |
39 |
Correct |
37 ms |
82372 KB |
Output is correct |
40 |
Correct |
37 ms |
82492 KB |
Output is correct |
41 |
Correct |
37 ms |
82464 KB |
Output is correct |
42 |
Correct |
37 ms |
82384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
36 ms |
82508 KB |
Output is correct |
2 |
Correct |
92 ms |
84264 KB |
Output is correct |
3 |
Correct |
64 ms |
84256 KB |
Output is correct |
4 |
Correct |
145 ms |
87108 KB |
Output is correct |
5 |
Correct |
96 ms |
87760 KB |
Output is correct |
6 |
Correct |
298 ms |
87020 KB |
Output is correct |
7 |
Correct |
74 ms |
84328 KB |
Output is correct |
8 |
Correct |
168 ms |
86980 KB |
Output is correct |
9 |
Correct |
127 ms |
87672 KB |
Output is correct |
10 |
Correct |
159 ms |
87744 KB |
Output is correct |
11 |
Correct |
195 ms |
85644 KB |
Output is correct |
12 |
Correct |
133 ms |
86844 KB |
Output is correct |
13 |
Correct |
155 ms |
85792 KB |
Output is correct |
14 |
Correct |
261 ms |
87132 KB |
Output is correct |
15 |
Correct |
271 ms |
87112 KB |
Output is correct |
16 |
Correct |
36 ms |
82500 KB |
Output is correct |
17 |
Correct |
38 ms |
82504 KB |
Output is correct |
18 |
Correct |
42 ms |
82372 KB |
Output is correct |
19 |
Correct |
38 ms |
82508 KB |
Output is correct |
20 |
Correct |
37 ms |
82384 KB |
Output is correct |
21 |
Correct |
38 ms |
82508 KB |
Output is correct |
22 |
Correct |
36 ms |
82372 KB |
Output is correct |
23 |
Correct |
37 ms |
82472 KB |
Output is correct |
24 |
Correct |
37 ms |
82380 KB |
Output is correct |
25 |
Correct |
37 ms |
82420 KB |
Output is correct |