| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 473405 |
2021-09-15T13:18:12 Z |
Hamed5001 |
Paths (BOI18_paths) |
C++14 |
|
473 ms |
95944 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mxN = 3e5+10;
/*
9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8
*/
ll dp[mxN][1<<5];
int color[mxN];
vector<int> adj[mxN];
int N, M, K;
ll dfs(int node, int msk) {
if (~dp[node][msk]) return dp[node][msk];
dp[node][msk] = 1;
int nmsk = msk | (1 << (color[node]-1));
for (auto c : adj[node]) {
if ((1<<(color[c]-1)) & nmsk) continue;
dp[node][msk] += dfs(c, nmsk);
}
return dp[node][msk];
}
void solve() {
memset(dp, -1, sizeof dp);
cin >> N >> M >> K;
for (int i = 1; i <= N; i++)
cin >> color[i];
for (int i = 0; i < M; i++) {
int u, v;
cin >> u >>v;
adj[u].push_back(v);
adj[v].push_back(u);
}
ll ans = 0;
for (int i = 1; i <= N; i++)
ans += dfs(i, 0);
cout << ans - N;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
82384 KB |
Output is correct |
| 2 |
Correct |
37 ms |
82416 KB |
Output is correct |
| 3 |
Correct |
38 ms |
82496 KB |
Output is correct |
| 4 |
Correct |
37 ms |
82376 KB |
Output is correct |
| 5 |
Correct |
37 ms |
82488 KB |
Output is correct |
| 6 |
Correct |
37 ms |
82512 KB |
Output is correct |
| 7 |
Correct |
37 ms |
82500 KB |
Output is correct |
| 8 |
Correct |
37 ms |
82424 KB |
Output is correct |
| 9 |
Correct |
38 ms |
82452 KB |
Output is correct |
| 10 |
Correct |
38 ms |
82404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
124 ms |
88944 KB |
Output is correct |
| 2 |
Correct |
109 ms |
88272 KB |
Output is correct |
| 3 |
Correct |
377 ms |
95944 KB |
Output is correct |
| 4 |
Correct |
151 ms |
90128 KB |
Output is correct |
| 5 |
Correct |
138 ms |
90232 KB |
Output is correct |
| 6 |
Correct |
288 ms |
93568 KB |
Output is correct |
| 7 |
Correct |
397 ms |
95172 KB |
Output is correct |
| 8 |
Correct |
346 ms |
95784 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
82384 KB |
Output is correct |
| 2 |
Correct |
37 ms |
82416 KB |
Output is correct |
| 3 |
Correct |
38 ms |
82496 KB |
Output is correct |
| 4 |
Correct |
37 ms |
82376 KB |
Output is correct |
| 5 |
Correct |
37 ms |
82488 KB |
Output is correct |
| 6 |
Correct |
37 ms |
82512 KB |
Output is correct |
| 7 |
Correct |
37 ms |
82500 KB |
Output is correct |
| 8 |
Correct |
37 ms |
82424 KB |
Output is correct |
| 9 |
Correct |
38 ms |
82452 KB |
Output is correct |
| 10 |
Correct |
38 ms |
82404 KB |
Output is correct |
| 11 |
Correct |
124 ms |
88944 KB |
Output is correct |
| 12 |
Correct |
109 ms |
88272 KB |
Output is correct |
| 13 |
Correct |
377 ms |
95944 KB |
Output is correct |
| 14 |
Correct |
151 ms |
90128 KB |
Output is correct |
| 15 |
Correct |
138 ms |
90232 KB |
Output is correct |
| 16 |
Correct |
288 ms |
93568 KB |
Output is correct |
| 17 |
Correct |
397 ms |
95172 KB |
Output is correct |
| 18 |
Correct |
346 ms |
95784 KB |
Output is correct |
| 19 |
Correct |
127 ms |
88912 KB |
Output is correct |
| 20 |
Correct |
108 ms |
88332 KB |
Output is correct |
| 21 |
Correct |
426 ms |
95208 KB |
Output is correct |
| 22 |
Correct |
153 ms |
90176 KB |
Output is correct |
| 23 |
Correct |
150 ms |
90244 KB |
Output is correct |
| 24 |
Correct |
271 ms |
93564 KB |
Output is correct |
| 25 |
Correct |
363 ms |
95112 KB |
Output is correct |
| 26 |
Correct |
351 ms |
95932 KB |
Output is correct |
| 27 |
Correct |
128 ms |
88372 KB |
Output is correct |
| 28 |
Correct |
148 ms |
89776 KB |
Output is correct |
| 29 |
Correct |
467 ms |
95348 KB |
Output is correct |
| 30 |
Correct |
328 ms |
92124 KB |
Output is correct |
| 31 |
Correct |
357 ms |
92096 KB |
Output is correct |
| 32 |
Correct |
473 ms |
95236 KB |
Output is correct |
| 33 |
Correct |
37 ms |
82488 KB |
Output is correct |
| 34 |
Correct |
38 ms |
82496 KB |
Output is correct |
| 35 |
Correct |
37 ms |
82472 KB |
Output is correct |
| 36 |
Correct |
38 ms |
82504 KB |
Output is correct |
| 37 |
Correct |
38 ms |
82464 KB |
Output is correct |
| 38 |
Correct |
37 ms |
82508 KB |
Output is correct |
| 39 |
Correct |
37 ms |
82428 KB |
Output is correct |
| 40 |
Correct |
36 ms |
82484 KB |
Output is correct |
| 41 |
Correct |
39 ms |
82432 KB |
Output is correct |
| 42 |
Correct |
38 ms |
82404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
82596 KB |
Output is correct |
| 2 |
Correct |
76 ms |
84352 KB |
Output is correct |
| 3 |
Correct |
61 ms |
84324 KB |
Output is correct |
| 4 |
Correct |
113 ms |
86944 KB |
Output is correct |
| 5 |
Correct |
92 ms |
87776 KB |
Output is correct |
| 6 |
Correct |
154 ms |
86972 KB |
Output is correct |
| 7 |
Correct |
66 ms |
84292 KB |
Output is correct |
| 8 |
Correct |
150 ms |
86920 KB |
Output is correct |
| 9 |
Correct |
101 ms |
87748 KB |
Output is correct |
| 10 |
Correct |
125 ms |
87772 KB |
Output is correct |
| 11 |
Correct |
135 ms |
85616 KB |
Output is correct |
| 12 |
Correct |
103 ms |
86764 KB |
Output is correct |
| 13 |
Correct |
115 ms |
85792 KB |
Output is correct |
| 14 |
Correct |
157 ms |
86984 KB |
Output is correct |
| 15 |
Correct |
128 ms |
87064 KB |
Output is correct |
| 16 |
Correct |
38 ms |
82508 KB |
Output is correct |
| 17 |
Correct |
37 ms |
82496 KB |
Output is correct |
| 18 |
Correct |
40 ms |
82416 KB |
Output is correct |
| 19 |
Correct |
39 ms |
82400 KB |
Output is correct |
| 20 |
Correct |
39 ms |
82372 KB |
Output is correct |
| 21 |
Correct |
39 ms |
82444 KB |
Output is correct |
| 22 |
Correct |
39 ms |
82508 KB |
Output is correct |
| 23 |
Correct |
38 ms |
82500 KB |
Output is correct |
| 24 |
Correct |
37 ms |
82488 KB |
Output is correct |
| 25 |
Correct |
38 ms |
82472 KB |
Output is correct |
