| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 185432 |
2020-01-11T16:57:05 Z |
AlexPop28 |
Paths (BOI18_paths) |
C++11 |
|
953 ms |
108396 KB |
#include <bits/stdc++.h>
#define dbg() cerr <<
#define name(x) (#x) << ": " << (x) << ' ' <<
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, k; cin >> n >> m >> k;
vector<int> col(n);
vector<vector<long long>> dp(n, vector<long long>(1 << k));
vector<vector<bool>> inq(n, vector<bool>(1 << k));
vector<pair<int, int>> q;
for (int i = 0; i < n; ++i) {
cin >> col[i]; --col[i];
q.emplace_back(i, 1 << col[i]);
dp[i][1 << col[i]] = 1;
inq[1][1 << col[i]] = true;
}
vector<vector<int>> adj(n);
for (int i = 0; i < m; ++i) {
int a, b; cin >> a >> b; --a, --b;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
}
long long ans = 0LL;
for (int it = 0; it < (int)q.size(); ++it) {
int node, mask; tie(node, mask) = q[it];
inq[node][mask] = false;
ans += dp[node][mask];
for (int &x : adj[node]) {
if ((1 << col[x]) & mask) continue;
int next = mask | (1 << col[x]);
dp[x][next] += dp[node][mask];
if (!inq[x][next]) {
q.emplace_back(x, next);
inq[x][next] = true;
}
}
}
cout << ans - n << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
12 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
380 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
120 ms |
8132 KB |
Output is correct |
| 2 |
Correct |
86 ms |
6300 KB |
Output is correct |
| 3 |
Correct |
658 ms |
81312 KB |
Output is correct |
| 4 |
Correct |
176 ms |
13684 KB |
Output is correct |
| 5 |
Correct |
147 ms |
12920 KB |
Output is correct |
| 6 |
Correct |
496 ms |
59820 KB |
Output is correct |
| 7 |
Correct |
660 ms |
81428 KB |
Output is correct |
| 8 |
Correct |
663 ms |
81888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
376 KB |
Output is correct |
| 3 |
Correct |
2 ms |
376 KB |
Output is correct |
| 4 |
Correct |
12 ms |
376 KB |
Output is correct |
| 5 |
Correct |
1 ms |
376 KB |
Output is correct |
| 6 |
Correct |
2 ms |
376 KB |
Output is correct |
| 7 |
Correct |
1 ms |
380 KB |
Output is correct |
| 8 |
Correct |
3 ms |
376 KB |
Output is correct |
| 9 |
Correct |
2 ms |
376 KB |
Output is correct |
| 10 |
Correct |
2 ms |
376 KB |
Output is correct |
| 11 |
Correct |
120 ms |
8132 KB |
Output is correct |
| 12 |
Correct |
86 ms |
6300 KB |
Output is correct |
| 13 |
Correct |
658 ms |
81312 KB |
Output is correct |
| 14 |
Correct |
176 ms |
13684 KB |
Output is correct |
| 15 |
Correct |
147 ms |
12920 KB |
Output is correct |
| 16 |
Correct |
496 ms |
59820 KB |
Output is correct |
| 17 |
Correct |
660 ms |
81428 KB |
Output is correct |
| 18 |
Correct |
663 ms |
81888 KB |
Output is correct |
| 19 |
Correct |
120 ms |
8200 KB |
Output is correct |
| 20 |
Correct |
86 ms |
6364 KB |
Output is correct |
| 21 |
Correct |
646 ms |
81296 KB |
Output is correct |
| 22 |
Correct |
171 ms |
13656 KB |
Output is correct |
| 23 |
Correct |
151 ms |
12892 KB |
Output is correct |
| 24 |
Correct |
477 ms |
59748 KB |
Output is correct |
| 25 |
Correct |
658 ms |
81376 KB |
Output is correct |
| 26 |
Correct |
615 ms |
82020 KB |
Output is correct |
| 27 |
Correct |
108 ms |
6492 KB |
Output is correct |
| 28 |
Correct |
184 ms |
10392 KB |
Output is correct |
| 29 |
Correct |
953 ms |
108372 KB |
Output is correct |
| 30 |
Correct |
701 ms |
58088 KB |
Output is correct |
| 31 |
Correct |
747 ms |
57824 KB |
Output is correct |
| 32 |
Correct |
906 ms |
108396 KB |
Output is correct |
| 33 |
Correct |
2 ms |
376 KB |
Output is correct |
| 34 |
Correct |
2 ms |
380 KB |
Output is correct |
| 35 |
Correct |
2 ms |
376 KB |
Output is correct |
| 36 |
Correct |
2 ms |
376 KB |
Output is correct |
| 37 |
Correct |
2 ms |
376 KB |
Output is correct |
| 38 |
Correct |
2 ms |
376 KB |
Output is correct |
| 39 |
Correct |
2 ms |
376 KB |
Output is correct |
| 40 |
Correct |
2 ms |
376 KB |
Output is correct |
| 41 |
Correct |
2 ms |
376 KB |
Output is correct |
| 42 |
Correct |
2 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
51 ms |
2496 KB |
Output is correct |
| 3 |
Correct |
28 ms |
2296 KB |
Output is correct |
| 4 |
Correct |
177 ms |
26452 KB |
Output is correct |
| 5 |
Correct |
146 ms |
27160 KB |
Output is correct |
| 6 |
Correct |
338 ms |
47344 KB |
Output is correct |
| 7 |
Correct |
36 ms |
2296 KB |
Output is correct |
| 8 |
Correct |
256 ms |
34768 KB |
Output is correct |
| 9 |
Correct |
191 ms |
35760 KB |
Output is correct |
| 10 |
Correct |
247 ms |
35692 KB |
Output is correct |
| 11 |
Correct |
213 ms |
26728 KB |
Output is correct |
| 12 |
Correct |
222 ms |
37608 KB |
Output is correct |
| 13 |
Correct |
227 ms |
27180 KB |
Output is correct |
| 14 |
Correct |
317 ms |
47340 KB |
Output is correct |
| 15 |
Correct |
255 ms |
47468 KB |
Output is correct |
| 16 |
Correct |
3 ms |
376 KB |
Output is correct |
| 17 |
Correct |
2 ms |
376 KB |
Output is correct |
| 18 |
Correct |
2 ms |
376 KB |
Output is correct |
| 19 |
Correct |
2 ms |
376 KB |
Output is correct |
| 20 |
Correct |
2 ms |
376 KB |
Output is correct |
| 21 |
Correct |
2 ms |
376 KB |
Output is correct |
| 22 |
Correct |
7 ms |
376 KB |
Output is correct |
| 23 |
Correct |
2 ms |
376 KB |
Output is correct |
| 24 |
Correct |
2 ms |
376 KB |
Output is correct |
| 25 |
Correct |
2 ms |
376 KB |
Output is correct |
