oj.uz

Submission #490602

# Submission time Handle Problem Language Result Execution time Memory
490602 2021-11-28T09:40:11 Z radal Paths (BOI18_paths) C++14
100 / 100
 348 ms 115948 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")
#define rep(i,l,r) for (int i = l; i < r; i++)
#define repr(i,r,l) for (int i = r; i >= l; i--)
#define X first
#define Y second
#define pb push_back
#define endl '\n'
#define debug(x) cerr << #x << " : " << x << endl;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pll;
typedef pair<long double,long double> pld;
const long long int N = 3e5+10,mod = 1e9+7,inf = 1e9,sq = 700,sig = 26;
inline int mkay(int a,int b){
    if (a+b >= mod) return a+b-mod;
    if (a+b < 0) return a+b+mod;
    return a+b;
}
inline int poww(int n,int k){
    int c = 1;
    while (k){
        if (k&1) c = (1ll*c*n)%mod;
        n = (1ll*n*n)%mod;
        k >>= 1;
    }
    return c;
}
ll dp[N][40];
vector<int> adj[N];
int c[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0);cout.tie(0);
    int n,m,k;
    cin >> n >> m >> k;
    rep(i,1,n+1){
        cin >> c[i];
        c[i]--;
    }
    rep(i,0,m){
        int u,v;
        cin >> v >> u;
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int y = (1 << k);
    rep(i,1,n+1) dp[i][(1 << c[i])] = 1;
    ll ans = 0;
    rep(j,1,y){
        rep(i,1,n+1){
            if ((j&(1 << c[i])) == 0) continue;
            int x = j-(1<< c[i]);
            if (!x) continue;
            for (int u : adj[i])
                dp[i][j] += dp[u][x];
            ans += dp[i][j];
        }
    }
    cout << ans;
    return 0;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 3 ms 7368 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 3 ms 7372 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 15316 KB Output is correct
2 Correct 46 ms 13388 KB Output is correct
3 Correct 262 ms 115400 KB Output is correct
4 Correct 86 ms 24660 KB Output is correct
5 Correct 100 ms 24580 KB Output is correct
6 Correct 176 ms 81852 KB Output is correct
7 Correct 268 ms 115288 KB Output is correct
8 Correct 296 ms 115948 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7372 KB Output is correct
3 Correct 4 ms 7372 KB Output is correct
4 Correct 5 ms 7372 KB Output is correct
5 Correct 3 ms 7368 KB Output is correct
6 Correct 4 ms 7372 KB Output is correct
7 Correct 4 ms 7372 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 3 ms 7372 KB Output is correct
11 Correct 74 ms 15316 KB Output is correct
12 Correct 46 ms 13388 KB Output is correct
13 Correct 262 ms 115400 KB Output is correct
14 Correct 86 ms 24660 KB Output is correct
15 Correct 100 ms 24580 KB Output is correct
16 Correct 176 ms 81852 KB Output is correct
17 Correct 268 ms 115288 KB Output is correct
18 Correct 296 ms 115948 KB Output is correct
19 Correct 63 ms 15336 KB Output is correct
20 Correct 53 ms 13488 KB Output is correct
21 Correct 266 ms 115296 KB Output is correct
22 Correct 100 ms 24644 KB Output is correct
23 Correct 85 ms 24604 KB Output is correct
24 Correct 183 ms 81900 KB Output is correct
25 Correct 272 ms 115192 KB Output is correct
26 Correct 281 ms 115868 KB Output is correct
27 Correct 56 ms 13364 KB Output is correct
28 Correct 77 ms 17100 KB Output is correct
29 Correct 348 ms 115184 KB Output is correct
30 Correct 230 ms 64720 KB Output is correct
31 Correct 212 ms 64828 KB Output is correct
32 Correct 317 ms 115232 KB Output is correct
33 Correct 4 ms 7292 KB Output is correct
34 Correct 4 ms 7368 KB Output is correct
35 Correct 4 ms 7372 KB Output is correct
36 Correct 4 ms 7372 KB Output is correct
37 Correct 4 ms 7372 KB Output is correct
38 Correct 4 ms 7372 KB Output is correct
39 Correct 4 ms 7372 KB Output is correct
40 Correct 4 ms 7376 KB Output is correct
41 Correct 4 ms 7372 KB Output is correct
42 Correct 4 ms 7244 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7376 KB Output is correct
2 Correct 21 ms 9276 KB Output is correct
3 Correct 18 ms 9292 KB Output is correct
4 Correct 64 ms 43080 KB Output is correct
5 Correct 61 ms 43892 KB Output is correct
6 Correct 155 ms 43208 KB Output is correct
7 Correct 20 ms 9292 KB Output is correct
8 Correct 97 ms 43176 KB Output is correct
9 Correct 67 ms 43932 KB Output is correct
10 Correct 83 ms 43724 KB Output is correct
11 Correct 66 ms 26184 KB Output is correct
12 Correct 78 ms 35188 KB Output is correct
13 Correct 77 ms 26272 KB Output is correct
14 Correct 127 ms 43200 KB Output is correct
15 Correct 131 ms 43292 KB Output is correct
16 Correct 4 ms 7372 KB Output is correct
17 Correct 4 ms 7372 KB Output is correct
18 Correct 5 ms 7372 KB Output is correct
19 Correct 4 ms 7368 KB Output is correct
20 Correct 4 ms 7372 KB Output is correct
21 Correct 5 ms 7380 KB Output is correct
22 Correct 5 ms 7400 KB Output is correct
23 Correct 4 ms 7380 KB Output is correct
24 Correct 5 ms 7252 KB Output is correct
25 Correct 4 ms 7372 KB Output is correct