| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 93703 |
2019-01-10T19:05:10 Z |
KLPP |
Paths (BOI18_paths) |
C++14 |
|
795 ms |
113796 KB |
#include<bits/stdc++.h>
using namespace std;
typedef long long int lld;
int n,m,k;
vector<int> nei[1000000];
int color[1000000];
lld DP[1000000][32];
lld compute(int pos, int msk){
if(DP[pos][msk]!=-1)return DP[pos][msk];
int c=color[pos];
int Bit=msk&(1<<c);
if(Bit==0){
DP[pos][msk]=0;
return 0;
}
DP[pos][msk]=0;
for(int i=0;i<nei[pos].size();i++){
DP[pos][msk]+=compute(nei[pos][i],msk-(1<<c));
}
return DP[pos][msk];
}
int main(){
cin>>n>>m>>k;
for(int i=0;i<n;i++){
cin>>color[i];
color[i]--;
}
for(int i=0;i<m;i++){
int x,y;
cin>>x>>y;
x--;
y--;
nei[x].push_back(y);
nei[y].push_back(x);
}
for(int i=0;i<n;i++){
for(int msk=0;msk<32;msk++)DP[i][msk]=-1;
DP[i][(1<<color[i])]=1;
}
lld ans=0;
for(int i=0;i<n;i++){
for(int msk=1;msk<(1<<k);msk++){ans+=compute(i,msk);
//cout<<compute(i,msk)<<" ";
}//cout<<endl;
}
ans-=n;
cout<<ans<<endl;
return 0;
}
Compilation message
paths.cpp: In function 'lld compute(int, int)':
paths.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<nei[pos].size();i++){
~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
37 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
19 ms |
23772 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 9 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
214 ms |
31624 KB |
Output is correct |
| 2 |
Correct |
162 ms |
29816 KB |
Output is correct |
| 3 |
Correct |
656 ms |
113016 KB |
Output is correct |
| 4 |
Correct |
289 ms |
39288 KB |
Output is correct |
| 5 |
Correct |
272 ms |
39364 KB |
Output is correct |
| 6 |
Correct |
493 ms |
85992 KB |
Output is correct |
| 7 |
Correct |
678 ms |
112992 KB |
Output is correct |
| 8 |
Correct |
635 ms |
113656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 2 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 3 |
Correct |
37 ms |
23800 KB |
Output is correct |
| 4 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 5 |
Correct |
19 ms |
23772 KB |
Output is correct |
| 6 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 7 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 8 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 9 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 10 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
214 ms |
31624 KB |
Output is correct |
| 12 |
Correct |
162 ms |
29816 KB |
Output is correct |
| 13 |
Correct |
656 ms |
113016 KB |
Output is correct |
| 14 |
Correct |
289 ms |
39288 KB |
Output is correct |
| 15 |
Correct |
272 ms |
39364 KB |
Output is correct |
| 16 |
Correct |
493 ms |
85992 KB |
Output is correct |
| 17 |
Correct |
678 ms |
112992 KB |
Output is correct |
| 18 |
Correct |
635 ms |
113656 KB |
Output is correct |
| 19 |
Correct |
201 ms |
31540 KB |
Output is correct |
| 20 |
Correct |
163 ms |
29884 KB |
Output is correct |
| 21 |
Correct |
680 ms |
113124 KB |
Output is correct |
| 22 |
Correct |
286 ms |
39288 KB |
Output is correct |
| 23 |
Correct |
261 ms |
39328 KB |
Output is correct |
| 24 |
Correct |
494 ms |
85868 KB |
Output is correct |
| 25 |
Correct |
568 ms |
113004 KB |
Output is correct |
| 26 |
Correct |
635 ms |
113796 KB |
Output is correct |
| 27 |
Correct |
166 ms |
29816 KB |
Output is correct |
| 28 |
Correct |
221 ms |
33144 KB |
Output is correct |
| 29 |
Correct |
751 ms |
113104 KB |
Output is correct |
| 30 |
Correct |
601 ms |
71916 KB |
Output is correct |
| 31 |
Correct |
608 ms |
71944 KB |
Output is correct |
| 32 |
Correct |
795 ms |
113372 KB |
Output is correct |
| 33 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 34 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 35 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 36 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 37 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 38 |
Correct |
22 ms |
23804 KB |
Output is correct |
| 39 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 40 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 41 |
Correct |
23 ms |
23772 KB |
Output is correct |
| 42 |
Correct |
22 ms |
23800 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 2 |
Correct |
74 ms |
25720 KB |
Output is correct |
| 3 |
Correct |
66 ms |
25724 KB |
Output is correct |
| 4 |
Correct |
196 ms |
53576 KB |
Output is correct |
| 5 |
Correct |
174 ms |
54260 KB |
Output is correct |
| 6 |
Correct |
265 ms |
53628 KB |
Output is correct |
| 7 |
Correct |
70 ms |
25720 KB |
Output is correct |
| 8 |
Correct |
242 ms |
53496 KB |
Output is correct |
| 9 |
Correct |
164 ms |
54156 KB |
Output is correct |
| 10 |
Correct |
168 ms |
54000 KB |
Output is correct |
| 11 |
Correct |
184 ms |
39668 KB |
Output is correct |
| 12 |
Correct |
190 ms |
46992 KB |
Output is correct |
| 13 |
Correct |
201 ms |
39708 KB |
Output is correct |
| 14 |
Correct |
279 ms |
53388 KB |
Output is correct |
| 15 |
Correct |
265 ms |
53624 KB |
Output is correct |
| 16 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 17 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 18 |
Correct |
22 ms |
23772 KB |
Output is correct |
| 19 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 20 |
Correct |
24 ms |
23800 KB |
Output is correct |
| 21 |
Correct |
23 ms |
23928 KB |
Output is correct |
| 22 |
Correct |
22 ms |
23800 KB |
Output is correct |
| 23 |
Correct |
22 ms |
23928 KB |
Output is correct |
| 24 |
Correct |
23 ms |
23800 KB |
Output is correct |
| 25 |
Correct |
22 ms |
23800 KB |
Output is correct |
