| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 94326 |
2019-01-17T17:56:32 Z |
dalgerok |
Paths (BOI18_paths) |
C++14 |
|
520 ms |
99576 KB |
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5, M = (1 << 5) + 1;
int n, m, k, a[N];
vector < int > g[N];
long long dp[M][N];
long long rec(int mask, int v){
if(dp[mask][v] != -1){
return dp[mask][v];
}
dp[mask][v] = 1;
for(int to : g[v]){
if(!((mask >> a[to]) & 1)){
dp[mask][v] += rec((mask | (1 << a[to])), to);
}
}
return dp[mask][v];
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> m >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
a[i] -= 1;
}
for(int i = 1; i <= m; i++){
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
long long ans = 0;
memset(dp, -1, sizeof(dp));
for(int i = 1; i <= n; i++){
ans += rec((1 << a[i]), i);
}
cout << ans - n;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
84988 KB |
Output is correct |
| 2 |
Correct |
60 ms |
84856 KB |
Output is correct |
| 3 |
Correct |
61 ms |
84856 KB |
Output is correct |
| 4 |
Correct |
60 ms |
85036 KB |
Output is correct |
| 5 |
Correct |
59 ms |
84856 KB |
Output is correct |
| 6 |
Correct |
60 ms |
84856 KB |
Output is correct |
| 7 |
Correct |
70 ms |
84856 KB |
Output is correct |
| 8 |
Correct |
59 ms |
84856 KB |
Output is correct |
| 9 |
Correct |
95 ms |
84856 KB |
Output is correct |
| 10 |
Correct |
60 ms |
84796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
91384 KB |
Output is correct |
| 2 |
Correct |
129 ms |
90620 KB |
Output is correct |
| 3 |
Correct |
466 ms |
98808 KB |
Output is correct |
| 4 |
Correct |
204 ms |
92792 KB |
Output is correct |
| 5 |
Correct |
181 ms |
92872 KB |
Output is correct |
| 6 |
Correct |
315 ms |
96872 KB |
Output is correct |
| 7 |
Correct |
335 ms |
98808 KB |
Output is correct |
| 8 |
Correct |
353 ms |
99568 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
60 ms |
84988 KB |
Output is correct |
| 2 |
Correct |
60 ms |
84856 KB |
Output is correct |
| 3 |
Correct |
61 ms |
84856 KB |
Output is correct |
| 4 |
Correct |
60 ms |
85036 KB |
Output is correct |
| 5 |
Correct |
59 ms |
84856 KB |
Output is correct |
| 6 |
Correct |
60 ms |
84856 KB |
Output is correct |
| 7 |
Correct |
70 ms |
84856 KB |
Output is correct |
| 8 |
Correct |
59 ms |
84856 KB |
Output is correct |
| 9 |
Correct |
95 ms |
84856 KB |
Output is correct |
| 10 |
Correct |
60 ms |
84796 KB |
Output is correct |
| 11 |
Correct |
140 ms |
91384 KB |
Output is correct |
| 12 |
Correct |
129 ms |
90620 KB |
Output is correct |
| 13 |
Correct |
466 ms |
98808 KB |
Output is correct |
| 14 |
Correct |
204 ms |
92792 KB |
Output is correct |
| 15 |
Correct |
181 ms |
92872 KB |
Output is correct |
| 16 |
Correct |
315 ms |
96872 KB |
Output is correct |
| 17 |
Correct |
335 ms |
98808 KB |
Output is correct |
| 18 |
Correct |
353 ms |
99568 KB |
Output is correct |
| 19 |
Correct |
138 ms |
91328 KB |
Output is correct |
| 20 |
Correct |
118 ms |
90688 KB |
Output is correct |
| 21 |
Correct |
340 ms |
99036 KB |
Output is correct |
| 22 |
Correct |
188 ms |
92940 KB |
Output is correct |
| 23 |
Correct |
179 ms |
92792 KB |
Output is correct |
| 24 |
Correct |
307 ms |
96980 KB |
Output is correct |
| 25 |
Correct |
426 ms |
98936 KB |
Output is correct |
| 26 |
Correct |
472 ms |
99576 KB |
Output is correct |
| 27 |
Correct |
147 ms |
90616 KB |
Output is correct |
| 28 |
Correct |
179 ms |
92148 KB |
Output is correct |
| 29 |
Correct |
520 ms |
98808 KB |
Output is correct |
| 30 |
Correct |
410 ms |
95336 KB |
Output is correct |
| 31 |
Correct |
381 ms |
95344 KB |
Output is correct |
| 32 |
Correct |
471 ms |
98936 KB |
Output is correct |
| 33 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 34 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 35 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 36 |
Correct |
69 ms |
84900 KB |
Output is correct |
| 37 |
Correct |
71 ms |
84856 KB |
Output is correct |
| 38 |
Correct |
70 ms |
84892 KB |
Output is correct |
| 39 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 40 |
Correct |
68 ms |
84856 KB |
Output is correct |
| 41 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 42 |
Correct |
68 ms |
84856 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
84856 KB |
Output is correct |
| 2 |
Correct |
93 ms |
86648 KB |
Output is correct |
| 3 |
Correct |
80 ms |
86648 KB |
Output is correct |
| 4 |
Correct |
124 ms |
89324 KB |
Output is correct |
| 5 |
Correct |
106 ms |
90160 KB |
Output is correct |
| 6 |
Correct |
166 ms |
89564 KB |
Output is correct |
| 7 |
Correct |
95 ms |
86724 KB |
Output is correct |
| 8 |
Correct |
136 ms |
89464 KB |
Output is correct |
| 9 |
Correct |
129 ms |
90212 KB |
Output is correct |
| 10 |
Correct |
146 ms |
90004 KB |
Output is correct |
| 11 |
Correct |
153 ms |
88008 KB |
Output is correct |
| 12 |
Correct |
116 ms |
89304 KB |
Output is correct |
| 13 |
Correct |
138 ms |
88216 KB |
Output is correct |
| 14 |
Correct |
168 ms |
89432 KB |
Output is correct |
| 15 |
Correct |
167 ms |
89424 KB |
Output is correct |
| 16 |
Correct |
68 ms |
84856 KB |
Output is correct |
| 17 |
Correct |
69 ms |
85032 KB |
Output is correct |
| 18 |
Correct |
68 ms |
84984 KB |
Output is correct |
| 19 |
Correct |
68 ms |
84856 KB |
Output is correct |
| 20 |
Correct |
69 ms |
84856 KB |
Output is correct |
| 21 |
Correct |
70 ms |
84856 KB |
Output is correct |
| 22 |
Correct |
71 ms |
84856 KB |
Output is correct |
| 23 |
Correct |
68 ms |
84856 KB |
Output is correct |
| 24 |
Correct |
69 ms |
84984 KB |
Output is correct |
| 25 |
Correct |
68 ms |
84856 KB |
Output is correct |
