# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
63176 | 2018-08-01T04:02:34 Z | 강태규(#1831) | Paths (BOI18_paths) | C++11 | 1008 ms | 69584 KB |
#include <iostream> #include <algorithm> #include <vector> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_map> #include <functional> #include <cstring> #include <cmath> #include <ctime> #include <cstdlib> using namespace std; typedef long long llong; typedef long double ld; typedef pair<int, int> pii; typedef pair<llong, llong> pll; int n, m, k; int col[300001]; vector<int> ps[6]; vector<int> edge[300001][6]; llong cnt[6][300001]; llong get(vector<int> cs) { llong ret = 0; int c = cs.size(); for (int i : ps[cs.back()]) cnt[c][i] = 0; for (int i : ps[cs.back()]) { for (int j : edge[i][cs[c - 2]]) { cnt[c][i] += cnt[c - 1][j]; } ret += cnt[c][i]; } return ret; } llong pro(vector<int> cs) { llong ret = 0; if (cs.size() > 1) ret += get(cs); for (int i = 1; i <= k; ++i) { int b = 0; for (int j : cs) { if (i == j) { b = 1; break; } } if (b) continue; cs.push_back(i); ret += pro(cs); cs.pop_back(); } return ret; } int main() { scanf("%d%d%d", &n, &m, &k); for (int i = 1; i <= n; ++i) { scanf("%d", col + i); ps[col[i]].push_back(i); cnt[1][i] = 1; } for (int i = 0; i < m; ++i) { int x, y; scanf("%d%d", &x, &y); edge[x][col[y]].push_back(y); edge[y][col[x]].push_back(x); } printf("%lld\n", pro(vector<int>())); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 42616 KB | Output is correct |
2 | Correct | 50 ms | 42616 KB | Output is correct |
3 | Correct | 48 ms | 42632 KB | Output is correct |
4 | Correct | 51 ms | 42760 KB | Output is correct |
5 | Correct | 43 ms | 42760 KB | Output is correct |
6 | Correct | 48 ms | 42760 KB | Output is correct |
7 | Correct | 49 ms | 42764 KB | Output is correct |
8 | Correct | 51 ms | 42788 KB | Output is correct |
9 | Correct | 50 ms | 42916 KB | Output is correct |
10 | Correct | 49 ms | 42916 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 298 ms | 47204 KB | Output is correct |
2 | Correct | 183 ms | 47204 KB | Output is correct |
3 | Correct | 694 ms | 66088 KB | Output is correct |
4 | Correct | 420 ms | 66088 KB | Output is correct |
5 | Correct | 368 ms | 66088 KB | Output is correct |
6 | Correct | 484 ms | 66088 KB | Output is correct |
7 | Correct | 663 ms | 66088 KB | Output is correct |
8 | Correct | 719 ms | 67204 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 49 ms | 42616 KB | Output is correct |
2 | Correct | 50 ms | 42616 KB | Output is correct |
3 | Correct | 48 ms | 42632 KB | Output is correct |
4 | Correct | 51 ms | 42760 KB | Output is correct |
5 | Correct | 43 ms | 42760 KB | Output is correct |
6 | Correct | 48 ms | 42760 KB | Output is correct |
7 | Correct | 49 ms | 42764 KB | Output is correct |
8 | Correct | 51 ms | 42788 KB | Output is correct |
9 | Correct | 50 ms | 42916 KB | Output is correct |
10 | Correct | 49 ms | 42916 KB | Output is correct |
11 | Correct | 298 ms | 47204 KB | Output is correct |
12 | Correct | 183 ms | 47204 KB | Output is correct |
13 | Correct | 694 ms | 66088 KB | Output is correct |
14 | Correct | 420 ms | 66088 KB | Output is correct |
15 | Correct | 368 ms | 66088 KB | Output is correct |
16 | Correct | 484 ms | 66088 KB | Output is correct |
17 | Correct | 663 ms | 66088 KB | Output is correct |
18 | Correct | 719 ms | 67204 KB | Output is correct |
19 | Correct | 272 ms | 67204 KB | Output is correct |
20 | Correct | 203 ms | 67204 KB | Output is correct |
21 | Correct | 697 ms | 67204 KB | Output is correct |
22 | Correct | 375 ms | 67204 KB | Output is correct |
23 | Correct | 361 ms | 67204 KB | Output is correct |
24 | Correct | 547 ms | 67204 KB | Output is correct |
25 | Correct | 728 ms | 67204 KB | Output is correct |
26 | Correct | 746 ms | 67204 KB | Output is correct |
27 | Correct | 179 ms | 67204 KB | Output is correct |
28 | Correct | 393 ms | 67204 KB | Output is correct |
29 | Correct | 931 ms | 69360 KB | Output is correct |
30 | Correct | 624 ms | 69360 KB | Output is correct |
31 | Correct | 757 ms | 69360 KB | Output is correct |
32 | Correct | 1008 ms | 69584 KB | Output is correct |
33 | Correct | 49 ms | 69584 KB | Output is correct |
34 | Correct | 50 ms | 69584 KB | Output is correct |
35 | Correct | 50 ms | 69584 KB | Output is correct |
36 | Correct | 48 ms | 69584 KB | Output is correct |
37 | Correct | 52 ms | 69584 KB | Output is correct |
38 | Correct | 54 ms | 69584 KB | Output is correct |
39 | Correct | 50 ms | 69584 KB | Output is correct |
40 | Correct | 57 ms | 69584 KB | Output is correct |
41 | Correct | 50 ms | 69584 KB | Output is correct |
42 | Correct | 59 ms | 69584 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 52 ms | 69584 KB | Output is correct |
2 | Correct | 108 ms | 69584 KB | Output is correct |
3 | Correct | 95 ms | 69584 KB | Output is correct |
4 | Correct | 248 ms | 69584 KB | Output is correct |
5 | Correct | 170 ms | 69584 KB | Output is correct |
6 | Correct | 720 ms | 69584 KB | Output is correct |
7 | Correct | 94 ms | 69584 KB | Output is correct |
8 | Correct | 309 ms | 69584 KB | Output is correct |
9 | Correct | 245 ms | 69584 KB | Output is correct |
10 | Correct | 273 ms | 69584 KB | Output is correct |
11 | Correct | 342 ms | 69584 KB | Output is correct |
12 | Correct | 372 ms | 69584 KB | Output is correct |
13 | Correct | 323 ms | 69584 KB | Output is correct |
14 | Correct | 596 ms | 69584 KB | Output is correct |
15 | Correct | 630 ms | 69584 KB | Output is correct |
16 | Correct | 50 ms | 69584 KB | Output is correct |
17 | Correct | 51 ms | 69584 KB | Output is correct |
18 | Correct | 52 ms | 69584 KB | Output is correct |
19 | Correct | 51 ms | 69584 KB | Output is correct |
20 | Correct | 50 ms | 69584 KB | Output is correct |
21 | Correct | 50 ms | 69584 KB | Output is correct |
22 | Correct | 51 ms | 69584 KB | Output is correct |
23 | Correct | 51 ms | 69584 KB | Output is correct |
24 | Correct | 49 ms | 69584 KB | Output is correct |
25 | Correct | 57 ms | 69584 KB | Output is correct |