| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 657732 |
2022-11-10T21:32:00 Z |
inksamurai |
Paths (BOI18_paths) |
C++17 |
|
744 ms |
64700 KB |
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3NRqilq ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
signed main(){
_3NRqilq;
int n,m,k;
cin>>n>>m>>k;
vi a(n);
rep(i,n){
cin>>a[i];
}
rep(i,n){
a[i]-=1;
}
vec(vi) adj(n);
rep(i,m){
int u,v;
cin>>u>>v;
u-=1,v-=1;
adj[u].pb(v);
adj[v].pb(u);
}
vec(vi) dp(1<<k,vi(n));
rep(i,n)dp[1<<a[i]][i]=1;
int ans=0;
rep(msk,1<<k){
rep(v,n){
for(auto u:adj[v]){
if(msk>>a[u]&1) continue;
int nmsk=msk|(1<<a[u]);
dp[nmsk][u]+=dp[msk][v];
}
}
rep(v,n){
ans+=dp[msk][v];
}
}
print(ans-n);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
10764 KB |
Output is correct |
| 2 |
Correct |
75 ms |
9704 KB |
Output is correct |
| 3 |
Correct |
479 ms |
45740 KB |
Output is correct |
| 4 |
Correct |
140 ms |
13880 KB |
Output is correct |
| 5 |
Correct |
96 ms |
13332 KB |
Output is correct |
| 6 |
Correct |
286 ms |
33516 KB |
Output is correct |
| 7 |
Correct |
459 ms |
45824 KB |
Output is correct |
| 8 |
Correct |
460 ms |
46400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
212 KB |
Output is correct |
| 10 |
Correct |
1 ms |
212 KB |
Output is correct |
| 11 |
Correct |
110 ms |
10764 KB |
Output is correct |
| 12 |
Correct |
75 ms |
9704 KB |
Output is correct |
| 13 |
Correct |
479 ms |
45740 KB |
Output is correct |
| 14 |
Correct |
140 ms |
13880 KB |
Output is correct |
| 15 |
Correct |
96 ms |
13332 KB |
Output is correct |
| 16 |
Correct |
286 ms |
33516 KB |
Output is correct |
| 17 |
Correct |
459 ms |
45824 KB |
Output is correct |
| 18 |
Correct |
460 ms |
46400 KB |
Output is correct |
| 19 |
Correct |
98 ms |
10832 KB |
Output is correct |
| 20 |
Correct |
77 ms |
9744 KB |
Output is correct |
| 21 |
Correct |
447 ms |
45792 KB |
Output is correct |
| 22 |
Correct |
122 ms |
13840 KB |
Output is correct |
| 23 |
Correct |
97 ms |
13376 KB |
Output is correct |
| 24 |
Correct |
288 ms |
33596 KB |
Output is correct |
| 25 |
Correct |
434 ms |
45836 KB |
Output is correct |
| 26 |
Correct |
479 ms |
46308 KB |
Output is correct |
| 27 |
Correct |
116 ms |
9768 KB |
Output is correct |
| 28 |
Correct |
145 ms |
13004 KB |
Output is correct |
| 29 |
Correct |
664 ms |
64700 KB |
Output is correct |
| 30 |
Correct |
405 ms |
37684 KB |
Output is correct |
| 31 |
Correct |
385 ms |
37804 KB |
Output is correct |
| 32 |
Correct |
744 ms |
64608 KB |
Output is correct |
| 33 |
Correct |
1 ms |
212 KB |
Output is correct |
| 34 |
Correct |
1 ms |
340 KB |
Output is correct |
| 35 |
Correct |
1 ms |
212 KB |
Output is correct |
| 36 |
Correct |
1 ms |
320 KB |
Output is correct |
| 37 |
Correct |
1 ms |
212 KB |
Output is correct |
| 38 |
Correct |
1 ms |
324 KB |
Output is correct |
| 39 |
Correct |
1 ms |
212 KB |
Output is correct |
| 40 |
Correct |
1 ms |
340 KB |
Output is correct |
| 41 |
Correct |
1 ms |
212 KB |
Output is correct |
| 42 |
Correct |
1 ms |
316 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
58 ms |
3360 KB |
Output is correct |
| 3 |
Correct |
25 ms |
3284 KB |
Output is correct |
| 4 |
Correct |
95 ms |
15308 KB |
Output is correct |
| 5 |
Correct |
66 ms |
15680 KB |
Output is correct |
| 6 |
Correct |
246 ms |
34188 KB |
Output is correct |
| 7 |
Correct |
37 ms |
3348 KB |
Output is correct |
| 8 |
Correct |
134 ms |
21640 KB |
Output is correct |
| 9 |
Correct |
94 ms |
22072 KB |
Output is correct |
| 10 |
Correct |
135 ms |
21772 KB |
Output is correct |
| 11 |
Correct |
124 ms |
18608 KB |
Output is correct |
| 12 |
Correct |
128 ms |
26552 KB |
Output is correct |
| 13 |
Correct |
122 ms |
18632 KB |
Output is correct |
| 14 |
Correct |
233 ms |
34172 KB |
Output is correct |
| 15 |
Correct |
254 ms |
34252 KB |
Output is correct |
| 16 |
Correct |
0 ms |
212 KB |
Output is correct |
| 17 |
Correct |
0 ms |
340 KB |
Output is correct |
| 18 |
Correct |
1 ms |
212 KB |
Output is correct |
| 19 |
Correct |
0 ms |
340 KB |
Output is correct |
| 20 |
Correct |
0 ms |
212 KB |
Output is correct |
| 21 |
Correct |
1 ms |
316 KB |
Output is correct |
| 22 |
Correct |
1 ms |
320 KB |
Output is correct |
| 23 |
Correct |
0 ms |
320 KB |
Output is correct |
| 24 |
Correct |
1 ms |
212 KB |
Output is correct |
| 25 |
Correct |
0 ms |
320 KB |
Output is correct |
