oj.uz

Submission #464006

# Submission time Handle Problem Language Result Execution time Memory
464006 2021-08-12T07:23:32 Z bonopo Paths (BOI18_paths) C++14
100 / 100
 591 ms 97108 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define pb push_back
#define rc (i<<1)|1
#define lc (i<<1)
#define el "\n"
#define f first
#define s second

typedef long long ll;
const int MM=3e5+5, MOD=1e9+7, LOG=19;
int N, M, K, c[MM]; ll dp[32][MM], ans;
vector<int> adj[MM];

ll dfs(int u, int mask) {
    if((mask&(1<<c[u]))==0) return 0;

    ll &ret=dp[mask][u];
    if(~ret) return ret;

    ret=0;
    for(int &v:adj[u]) if(mask&(1<<c[v])) ret+=+dfs(v, mask^(1<<c[u]));
    return ret;
}

int32_t main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    cin>>N>>M>>K;
    memset(dp, -1, sizeof(dp));
    for(int i=1; i<=N; ++i) cin>>c[i], --c[i], dp[1<<c[i]][i]=1;
    for(int i=1, u, v; i<=M; ++i) {
        cin>>u>>v;
        adj[u].pb(v); adj[v].pb(u); }
    for(int i=1; i<=N; ++i) for(int k=0; k<(1<<K); ++k) ans+=dfs(i, k);
    cout<<ans-N<<el;
}

// MM

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82476 KB Output is correct
2 Correct 36 ms 82508 KB Output is correct
3 Correct 36 ms 82408 KB Output is correct
4 Correct 35 ms 82496 KB Output is correct
5 Correct 37 ms 82460 KB Output is correct
6 Correct 36 ms 82500 KB Output is correct
7 Correct 37 ms 82444 KB Output is correct
8 Correct 36 ms 82508 KB Output is correct
9 Correct 35 ms 82520 KB Output is correct
10 Correct 35 ms 82372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 88900 KB Output is correct
2 Correct 119 ms 88324 KB Output is correct
3 Correct 421 ms 96436 KB Output is correct
4 Correct 187 ms 90328 KB Output is correct
5 Correct 156 ms 90352 KB Output is correct
6 Correct 294 ms 94408 KB Output is correct
7 Correct 391 ms 96456 KB Output is correct
8 Correct 403 ms 97092 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82476 KB Output is correct
2 Correct 36 ms 82508 KB Output is correct
3 Correct 36 ms 82408 KB Output is correct
4 Correct 35 ms 82496 KB Output is correct
5 Correct 37 ms 82460 KB Output is correct
6 Correct 36 ms 82500 KB Output is correct
7 Correct 37 ms 82444 KB Output is correct
8 Correct 36 ms 82508 KB Output is correct
9 Correct 35 ms 82520 KB Output is correct
10 Correct 35 ms 82372 KB Output is correct
11 Correct 129 ms 88900 KB Output is correct
12 Correct 119 ms 88324 KB Output is correct
13 Correct 421 ms 96436 KB Output is correct
14 Correct 187 ms 90328 KB Output is correct
15 Correct 156 ms 90352 KB Output is correct
16 Correct 294 ms 94408 KB Output is correct
17 Correct 391 ms 96456 KB Output is correct
18 Correct 403 ms 97092 KB Output is correct
19 Correct 144 ms 88900 KB Output is correct
20 Correct 120 ms 88356 KB Output is correct
21 Correct 421 ms 96500 KB Output is correct
22 Correct 151 ms 90308 KB Output is correct
23 Correct 137 ms 90408 KB Output is correct
24 Correct 305 ms 94440 KB Output is correct
25 Correct 412 ms 96496 KB Output is correct
26 Correct 398 ms 97108 KB Output is correct
27 Correct 146 ms 88268 KB Output is correct
28 Correct 173 ms 89780 KB Output is correct
29 Correct 591 ms 96472 KB Output is correct
30 Correct 415 ms 92920 KB Output is correct
31 Correct 395 ms 92860 KB Output is correct
32 Correct 577 ms 96504 KB Output is correct
33 Correct 39 ms 82372 KB Output is correct
34 Correct 40 ms 82384 KB Output is correct
35 Correct 37 ms 82480 KB Output is correct
36 Correct 38 ms 82500 KB Output is correct
37 Correct 38 ms 82532 KB Output is correct
38 Correct 39 ms 82388 KB Output is correct
39 Correct 37 ms 82372 KB Output is correct
40 Correct 37 ms 82492 KB Output is correct
41 Correct 37 ms 82464 KB Output is correct
42 Correct 37 ms 82384 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82508 KB Output is correct
2 Correct 92 ms 84264 KB Output is correct
3 Correct 64 ms 84256 KB Output is correct
4 Correct 145 ms 87108 KB Output is correct
5 Correct 96 ms 87760 KB Output is correct
6 Correct 298 ms 87020 KB Output is correct
7 Correct 74 ms 84328 KB Output is correct
8 Correct 168 ms 86980 KB Output is correct
9 Correct 127 ms 87672 KB Output is correct
10 Correct 159 ms 87744 KB Output is correct
11 Correct 195 ms 85644 KB Output is correct
12 Correct 133 ms 86844 KB Output is correct
13 Correct 155 ms 85792 KB Output is correct
14 Correct 261 ms 87132 KB Output is correct
15 Correct 271 ms 87112 KB Output is correct
16 Correct 36 ms 82500 KB Output is correct
17 Correct 38 ms 82504 KB Output is correct
18 Correct 42 ms 82372 KB Output is correct
19 Correct 38 ms 82508 KB Output is correct
20 Correct 37 ms 82384 KB Output is correct
21 Correct 38 ms 82508 KB Output is correct
22 Correct 36 ms 82372 KB Output is correct
23 Correct 37 ms 82472 KB Output is correct
24 Correct 37 ms 82380 KB Output is correct
25 Correct 37 ms 82420 KB Output is correct