oj.uz

Submission #448610

# Submission time Handle Problem Language Result Execution time Memory
448610 2021-07-31T07:28:32 Z Killer2501 Paths (BOI18_paths) C++14
100 / 100
 518 ms 112168 KB 
#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int  N = 3e5+55;
const ll mod = 1e9+7;
const ll mod1 = 1e9+1;
const ll base = 311;
const ll base1 = 331;
ll m, n, t, k, a[N], tong, b[N], dp[N][33], c[N], lab[N], cnt, ans, h[N], d[N];
priority_queue< pll, vector<pll>, greater<pll> > pq;
string s[N];
vector<ll> adj[N];
vector<pll> e;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

ll cal(ll u, ll mask)
{
    if(dp[u][mask] != -1)return dp[u][mask];
    ll total = 1;
    for(ll v : adj[u])
    {
        if((mask >> a[v]) & 1)continue;
        total += cal(v, mask | (1<<a[v]));
    }
    return dp[u][mask] = total;
}
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];
    }
    while(m -- > 0)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    memset(dp, -1, sizeof(dp));
    for(int i = 1; i <= n; i ++)
    {
        ans += cal(i, (1<<a[i]));
    }
    cout << ans-n;
}
/*
1
5 9
1 2 3 2
1 3 2 -2
2 2 3
1 3 2 -3
2 2 3
1 1 4 7
1 4 5 8
2 5 2
2 5 1
1 5 6
1 1 2 2
1 2 4 3
2 1 4
1 1 5 6
1 2 3 -2
2 3 5
*/

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94148 KB Output is correct
2 Correct 45 ms 94264 KB Output is correct
3 Correct 43 ms 94232 KB Output is correct
4 Correct 42 ms 94196 KB Output is correct
5 Correct 41 ms 94208 KB Output is correct
6 Correct 40 ms 94224 KB Output is correct
7 Correct 41 ms 94284 KB Output is correct
8 Correct 41 ms 94232 KB Output is correct
9 Correct 42 ms 94276 KB Output is correct
10 Correct 41 ms 94168 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 101512 KB Output is correct
2 Correct 116 ms 101368 KB Output is correct
3 Correct 433 ms 110972 KB Output is correct
4 Correct 179 ms 106084 KB Output is correct
5 Correct 157 ms 105916 KB Output is correct
6 Correct 334 ms 108808 KB Output is correct
7 Correct 409 ms 111624 KB Output is correct
8 Correct 438 ms 112168 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 94148 KB Output is correct
2 Correct 45 ms 94264 KB Output is correct
3 Correct 43 ms 94232 KB Output is correct
4 Correct 42 ms 94196 KB Output is correct
5 Correct 41 ms 94208 KB Output is correct
6 Correct 40 ms 94224 KB Output is correct
7 Correct 41 ms 94284 KB Output is correct
8 Correct 41 ms 94232 KB Output is correct
9 Correct 42 ms 94276 KB Output is correct
10 Correct 41 ms 94168 KB Output is correct
11 Correct 185 ms 101512 KB Output is correct
12 Correct 116 ms 101368 KB Output is correct
13 Correct 433 ms 110972 KB Output is correct
14 Correct 179 ms 106084 KB Output is correct
15 Correct 157 ms 105916 KB Output is correct
16 Correct 334 ms 108808 KB Output is correct
17 Correct 409 ms 111624 KB Output is correct
18 Correct 438 ms 112168 KB Output is correct
19 Correct 132 ms 104284 KB Output is correct
20 Correct 112 ms 103676 KB Output is correct
21 Correct 398 ms 111632 KB Output is correct
22 Correct 175 ms 105988 KB Output is correct
23 Correct 157 ms 106028 KB Output is correct
24 Correct 283 ms 108752 KB Output is correct
25 Correct 419 ms 111556 KB Output is correct
26 Correct 376 ms 112068 KB Output is correct
27 Correct 125 ms 103624 KB Output is correct
28 Correct 157 ms 105860 KB Output is correct
29 Correct 504 ms 111596 KB Output is correct
30 Correct 363 ms 108208 KB Output is correct
31 Correct 410 ms 108264 KB Output is correct
32 Correct 518 ms 111680 KB Output is correct
33 Correct 48 ms 94232 KB Output is correct
34 Correct 42 ms 94352 KB Output is correct
35 Correct 40 ms 94256 KB Output is correct
36 Correct 42 ms 94192 KB Output is correct
37 Correct 47 ms 94296 KB Output is correct
38 Correct 47 ms 94276 KB Output is correct
39 Correct 48 ms 94192 KB Output is correct
40 Correct 41 ms 94196 KB Output is correct
41 Correct 42 ms 94192 KB Output is correct
42 Correct 42 ms 94276 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 94192 KB Output is correct
2 Correct 79 ms 96364 KB Output is correct
3 Correct 64 ms 96456 KB Output is correct
4 Correct 125 ms 98492 KB Output is correct
5 Correct 101 ms 99048 KB Output is correct
6 Correct 156 ms 98496 KB Output is correct
7 Correct 69 ms 96368 KB Output is correct
8 Correct 155 ms 98564 KB Output is correct
9 Correct 107 ms 98876 KB Output is correct
10 Correct 131 ms 98664 KB Output is correct
11 Correct 149 ms 97204 KB Output is correct
12 Correct 114 ms 97900 KB Output is correct
13 Correct 125 ms 97408 KB Output is correct
14 Correct 176 ms 98580 KB Output is correct
15 Correct 145 ms 98648 KB Output is correct
16 Correct 42 ms 94280 KB Output is correct
17 Correct 42 ms 94184 KB Output is correct
18 Correct 43 ms 94224 KB Output is correct
19 Correct 42 ms 94276 KB Output is correct
20 Correct 42 ms 94284 KB Output is correct
21 Correct 42 ms 94232 KB Output is correct
22 Correct 44 ms 94276 KB Output is correct
23 Correct 45 ms 94256 KB Output is correct
24 Correct 42 ms 94248 KB Output is correct
25 Correct 44 ms 94224 KB Output is correct