| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 392130 |
2021-04-20T14:30:46 Z |
Victor |
Paths (BOI18_paths) |
C++17 |
|
475 ms |
98528 KB |
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = a; i < b; ++i)
#define per(i, a, b) for (int i = b - 1; i >= a; --i)
#define trav(a, x) for (auto& a : x)
#define sz(a) a.size()
#define umap unordered_map
#define uset unordered_set
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
vi graph[300001];
ll memo[300001][32];
int colors[300001];
ll dp(int u, int mask) {
ll& ans = memo[u][mask];
if (ans != -1) return ans;
ans = 1;
trav(v, graph[u])if(mask&(1<<colors[v]))ans+=dp(v,mask^(1<<colors[v]));
return ans;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
memset(memo, -1, sizeof(memo));
int n, m, k;
cin >> n >> m >> k;
rep(i, 0, n) {
cin>>colors[i];
--colors[i];
graph[n].push_back(i);
}
rep(i, 0, m) {
int u, v;
cin >> u >> v;
graph[--u].push_back(--v);
graph[v].push_back(u);
}
cout<<dp(n, (1 << k) - 1) - n - 1<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
82500 KB |
Output is correct |
| 2 |
Correct |
42 ms |
82376 KB |
Output is correct |
| 3 |
Correct |
43 ms |
82452 KB |
Output is correct |
| 4 |
Correct |
42 ms |
82388 KB |
Output is correct |
| 5 |
Correct |
43 ms |
82472 KB |
Output is correct |
| 6 |
Correct |
59 ms |
82372 KB |
Output is correct |
| 7 |
Correct |
41 ms |
82440 KB |
Output is correct |
| 8 |
Correct |
43 ms |
82532 KB |
Output is correct |
| 9 |
Correct |
41 ms |
82392 KB |
Output is correct |
| 10 |
Correct |
42 ms |
82372 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
123 ms |
88892 KB |
Output is correct |
| 2 |
Correct |
109 ms |
88232 KB |
Output is correct |
| 3 |
Correct |
402 ms |
97592 KB |
Output is correct |
| 4 |
Correct |
154 ms |
90564 KB |
Output is correct |
| 5 |
Correct |
136 ms |
90436 KB |
Output is correct |
| 6 |
Correct |
279 ms |
95292 KB |
Output is correct |
| 7 |
Correct |
394 ms |
97696 KB |
Output is correct |
| 8 |
Correct |
379 ms |
98416 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
42 ms |
82500 KB |
Output is correct |
| 2 |
Correct |
42 ms |
82376 KB |
Output is correct |
| 3 |
Correct |
43 ms |
82452 KB |
Output is correct |
| 4 |
Correct |
42 ms |
82388 KB |
Output is correct |
| 5 |
Correct |
43 ms |
82472 KB |
Output is correct |
| 6 |
Correct |
59 ms |
82372 KB |
Output is correct |
| 7 |
Correct |
41 ms |
82440 KB |
Output is correct |
| 8 |
Correct |
43 ms |
82532 KB |
Output is correct |
| 9 |
Correct |
41 ms |
82392 KB |
Output is correct |
| 10 |
Correct |
42 ms |
82372 KB |
Output is correct |
| 11 |
Correct |
123 ms |
88892 KB |
Output is correct |
| 12 |
Correct |
109 ms |
88232 KB |
Output is correct |
| 13 |
Correct |
402 ms |
97592 KB |
Output is correct |
| 14 |
Correct |
154 ms |
90564 KB |
Output is correct |
| 15 |
Correct |
136 ms |
90436 KB |
Output is correct |
| 16 |
Correct |
279 ms |
95292 KB |
Output is correct |
| 17 |
Correct |
394 ms |
97696 KB |
Output is correct |
| 18 |
Correct |
379 ms |
98416 KB |
Output is correct |
| 19 |
Correct |
125 ms |
89028 KB |
Output is correct |
| 20 |
Correct |
109 ms |
88288 KB |
Output is correct |
| 21 |
Correct |
402 ms |
97732 KB |
Output is correct |
| 22 |
Correct |
151 ms |
90392 KB |
Output is correct |
| 23 |
Correct |
133 ms |
90404 KB |
Output is correct |
| 24 |
Correct |
291 ms |
95168 KB |
Output is correct |
| 25 |
Correct |
385 ms |
97804 KB |
Output is correct |
| 26 |
Correct |
376 ms |
98528 KB |
Output is correct |
| 27 |
Correct |
128 ms |
88272 KB |
Output is correct |
| 28 |
Correct |
163 ms |
89772 KB |
Output is correct |
| 29 |
Correct |
475 ms |
97792 KB |
Output is correct |
| 30 |
Correct |
364 ms |
93692 KB |
Output is correct |
| 31 |
Correct |
386 ms |
93540 KB |
Output is correct |
| 32 |
Correct |
465 ms |
97700 KB |
Output is correct |
| 33 |
Correct |
43 ms |
82424 KB |
Output is correct |
| 34 |
Correct |
42 ms |
82452 KB |
Output is correct |
| 35 |
Correct |
44 ms |
82480 KB |
Output is correct |
| 36 |
Correct |
42 ms |
82476 KB |
Output is correct |
| 37 |
Correct |
42 ms |
82480 KB |
Output is correct |
| 38 |
Correct |
41 ms |
82500 KB |
Output is correct |
| 39 |
Correct |
44 ms |
82460 KB |
Output is correct |
| 40 |
Correct |
43 ms |
82444 KB |
Output is correct |
| 41 |
Correct |
42 ms |
82460 KB |
Output is correct |
| 42 |
Correct |
43 ms |
82500 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
82464 KB |
Output is correct |
| 2 |
Correct |
79 ms |
84228 KB |
Output is correct |
| 3 |
Correct |
64 ms |
84252 KB |
Output is correct |
| 4 |
Correct |
127 ms |
87364 KB |
Output is correct |
| 5 |
Correct |
100 ms |
88136 KB |
Output is correct |
| 6 |
Correct |
163 ms |
87360 KB |
Output is correct |
| 7 |
Correct |
82 ms |
84272 KB |
Output is correct |
| 8 |
Correct |
137 ms |
87440 KB |
Output is correct |
| 9 |
Correct |
111 ms |
88132 KB |
Output is correct |
| 10 |
Correct |
137 ms |
88268 KB |
Output is correct |
| 11 |
Correct |
149 ms |
85836 KB |
Output is correct |
| 12 |
Correct |
120 ms |
87112 KB |
Output is correct |
| 13 |
Correct |
129 ms |
85972 KB |
Output is correct |
| 14 |
Correct |
163 ms |
87352 KB |
Output is correct |
| 15 |
Correct |
148 ms |
87492 KB |
Output is correct |
| 16 |
Correct |
49 ms |
82500 KB |
Output is correct |
| 17 |
Correct |
43 ms |
82484 KB |
Output is correct |
| 18 |
Correct |
42 ms |
82500 KB |
Output is correct |
| 19 |
Correct |
43 ms |
82468 KB |
Output is correct |
| 20 |
Correct |
45 ms |
82372 KB |
Output is correct |
| 21 |
Correct |
43 ms |
82500 KB |
Output is correct |
| 22 |
Correct |
43 ms |
82436 KB |
Output is correct |
| 23 |
Correct |
42 ms |
82432 KB |
Output is correct |
| 24 |
Correct |
42 ms |
82412 KB |
Output is correct |
| 25 |
Correct |
40 ms |
82420 KB |
Output is correct |
