| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 160283 |
2019-10-26T18:02:14 Z |
pamaj |
Paths (BOI18_paths) |
C++14 |
|
563 ms |
173560 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
typedef long long ll;
int n, m, k;
int cor[maxn];
int dp[maxn][129];
bool vis[maxn];
vector<int> G[maxn];
inline ll dfs(int x, int mask)
{
//if(mask == (1 << (k + 1)) - 1) return 1;
if(dp[x][mask] != -1) return dp[x][mask];
ll cont = 0;
for(auto u : G[x])
{
if((mask & (1 << cor[u])) == 0)
{
cont += 1 + dfs(u, (mask | (1 << cor[u])));
}
//cont += dfs(u, (1 << cor[u]));
}
return dp[x][mask] = cont;
}
int main()
{
ios::sync_with_stdio(false), cin.tie(nullptr);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++)
cin >> cor[i];
for(int i = 0; i < m; i++)
{
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
memset(dp, -1, sizeof(dp));
ll ans = 0;
for(int i = 1; i <= n; i++)
{
ans += dfs(i, 1 << cor[i]);
}
cout << ans << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
159036 KB |
Output is correct |
| 2 |
Correct |
209 ms |
158968 KB |
Output is correct |
| 3 |
Correct |
143 ms |
158940 KB |
Output is correct |
| 4 |
Correct |
140 ms |
158832 KB |
Output is correct |
| 5 |
Correct |
143 ms |
158852 KB |
Output is correct |
| 6 |
Correct |
142 ms |
158904 KB |
Output is correct |
| 7 |
Correct |
141 ms |
158840 KB |
Output is correct |
| 8 |
Correct |
138 ms |
158812 KB |
Output is correct |
| 9 |
Correct |
149 ms |
158908 KB |
Output is correct |
| 10 |
Correct |
140 ms |
158872 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
240 ms |
165368 KB |
Output is correct |
| 2 |
Correct |
223 ms |
164724 KB |
Output is correct |
| 3 |
Correct |
509 ms |
173032 KB |
Output is correct |
| 4 |
Correct |
282 ms |
166800 KB |
Output is correct |
| 5 |
Correct |
307 ms |
166984 KB |
Output is correct |
| 6 |
Correct |
514 ms |
170868 KB |
Output is correct |
| 7 |
Correct |
503 ms |
173052 KB |
Output is correct |
| 8 |
Correct |
498 ms |
173556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
159036 KB |
Output is correct |
| 2 |
Correct |
209 ms |
158968 KB |
Output is correct |
| 3 |
Correct |
143 ms |
158940 KB |
Output is correct |
| 4 |
Correct |
140 ms |
158832 KB |
Output is correct |
| 5 |
Correct |
143 ms |
158852 KB |
Output is correct |
| 6 |
Correct |
142 ms |
158904 KB |
Output is correct |
| 7 |
Correct |
141 ms |
158840 KB |
Output is correct |
| 8 |
Correct |
138 ms |
158812 KB |
Output is correct |
| 9 |
Correct |
149 ms |
158908 KB |
Output is correct |
| 10 |
Correct |
140 ms |
158872 KB |
Output is correct |
| 11 |
Correct |
240 ms |
165368 KB |
Output is correct |
| 12 |
Correct |
223 ms |
164724 KB |
Output is correct |
| 13 |
Correct |
509 ms |
173032 KB |
Output is correct |
| 14 |
Correct |
282 ms |
166800 KB |
Output is correct |
| 15 |
Correct |
307 ms |
166984 KB |
Output is correct |
| 16 |
Correct |
514 ms |
170868 KB |
Output is correct |
| 17 |
Correct |
503 ms |
173052 KB |
Output is correct |
| 18 |
Correct |
498 ms |
173556 KB |
Output is correct |
| 19 |
Correct |
240 ms |
165340 KB |
Output is correct |
| 20 |
Correct |
218 ms |
164748 KB |
Output is correct |
| 21 |
Correct |
507 ms |
173048 KB |
Output is correct |
| 22 |
Correct |
318 ms |
166848 KB |
Output is correct |
| 23 |
Correct |
253 ms |
166932 KB |
Output is correct |
| 24 |
Correct |
402 ms |
170860 KB |
Output is correct |
| 25 |
Correct |
498 ms |
172968 KB |
Output is correct |
| 26 |
Correct |
484 ms |
173560 KB |
Output is correct |
| 27 |
Correct |
241 ms |
164772 KB |
Output is correct |
| 28 |
Correct |
263 ms |
166152 KB |
Output is correct |
| 29 |
Correct |
563 ms |
173044 KB |
Output is correct |
| 30 |
Correct |
469 ms |
169324 KB |
Output is correct |
| 31 |
Correct |
495 ms |
169364 KB |
Output is correct |
| 32 |
Correct |
559 ms |
173048 KB |
Output is correct |
| 33 |
Correct |
132 ms |
158940 KB |
Output is correct |
| 34 |
Correct |
136 ms |
158840 KB |
Output is correct |
| 35 |
Correct |
133 ms |
158944 KB |
Output is correct |
| 36 |
Correct |
136 ms |
158824 KB |
Output is correct |
| 37 |
Correct |
134 ms |
158916 KB |
Output is correct |
| 38 |
Correct |
147 ms |
158812 KB |
Output is correct |
| 39 |
Correct |
134 ms |
158828 KB |
Output is correct |
| 40 |
Correct |
154 ms |
158896 KB |
Output is correct |
| 41 |
Correct |
136 ms |
158936 KB |
Output is correct |
| 42 |
Correct |
143 ms |
158800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
137 ms |
158840 KB |
Output is correct |
| 2 |
Correct |
187 ms |
160624 KB |
Output is correct |
| 3 |
Correct |
170 ms |
160748 KB |
Output is correct |
| 4 |
Correct |
227 ms |
163464 KB |
Output is correct |
| 5 |
Correct |
205 ms |
164208 KB |
Output is correct |
| 6 |
Correct |
250 ms |
163420 KB |
Output is correct |
| 7 |
Correct |
173 ms |
160888 KB |
Output is correct |
| 8 |
Correct |
232 ms |
163460 KB |
Output is correct |
| 9 |
Correct |
202 ms |
164184 KB |
Output is correct |
| 10 |
Correct |
228 ms |
164024 KB |
Output is correct |
| 11 |
Correct |
236 ms |
162036 KB |
Output is correct |
| 12 |
Correct |
209 ms |
163184 KB |
Output is correct |
| 13 |
Correct |
222 ms |
162296 KB |
Output is correct |
| 14 |
Correct |
255 ms |
163448 KB |
Output is correct |
| 15 |
Correct |
235 ms |
163544 KB |
Output is correct |
| 16 |
Correct |
134 ms |
158792 KB |
Output is correct |
| 17 |
Correct |
137 ms |
158808 KB |
Output is correct |
| 18 |
Correct |
135 ms |
158940 KB |
Output is correct |
| 19 |
Correct |
140 ms |
158888 KB |
Output is correct |
| 20 |
Correct |
139 ms |
158816 KB |
Output is correct |
| 21 |
Correct |
138 ms |
158840 KB |
Output is correct |
| 22 |
Correct |
134 ms |
158856 KB |
Output is correct |
| 23 |
Correct |
136 ms |
158840 KB |
Output is correct |
| 24 |
Correct |
134 ms |
158840 KB |
Output is correct |
| 25 |
Correct |
133 ms |
158840 KB |
Output is correct |
