oj.uz

Submission #448608

# Submission time Handle Problem Language Result Execution time Memory
448608 2021-07-31T07:27:38 Z Killer2501 Paths (BOI18_paths) C++14
53 / 100
 161 ms 72904 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 = 2e5+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 28 ms 62924 KB Output is correct
2 Correct 28 ms 62960 KB Output is correct
3 Correct 28 ms 62924 KB Output is correct
4 Correct 31 ms 62840 KB Output is correct
5 Correct 28 ms 62908 KB Output is correct
6 Correct 27 ms 62940 KB Output is correct
7 Correct 28 ms 62944 KB Output is correct
8 Correct 29 ms 63036 KB Output is correct
9 Correct 28 ms 62868 KB Output is correct
10 Correct 28 ms 62844 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 72904 KB Output is correct
2 Correct 108 ms 72344 KB Output is correct
3 Runtime error 48 ms 28936 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 62924 KB Output is correct
2 Correct 28 ms 62960 KB Output is correct
3 Correct 28 ms 62924 KB Output is correct
4 Correct 31 ms 62840 KB Output is correct
5 Correct 28 ms 62908 KB Output is correct
6 Correct 27 ms 62940 KB Output is correct
7 Correct 28 ms 62944 KB Output is correct
8 Correct 29 ms 63036 KB Output is correct
9 Correct 28 ms 62868 KB Output is correct
10 Correct 28 ms 62844 KB Output is correct
11 Correct 117 ms 72904 KB Output is correct
12 Correct 108 ms 72344 KB Output is correct
13 Runtime error 48 ms 28936 KB Execution killed with signal 6
14 Halted 0 ms 0 KB -

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 62864 KB Output is correct
2 Correct 67 ms 65884 KB Output is correct
3 Correct 56 ms 65816 KB Output is correct
4 Correct 126 ms 68548 KB Output is correct
5 Correct 96 ms 69056 KB Output is correct
6 Correct 154 ms 68540 KB Output is correct
7 Correct 57 ms 65820 KB Output is correct
8 Correct 131 ms 68548 KB Output is correct
9 Correct 94 ms 68912 KB Output is correct
10 Correct 122 ms 68664 KB Output is correct
11 Correct 152 ms 67184 KB Output is correct
12 Correct 98 ms 67988 KB Output is correct
13 Correct 111 ms 67252 KB Output is correct
14 Correct 161 ms 68700 KB Output is correct
15 Correct 138 ms 68684 KB Output is correct
16 Correct 27 ms 62924 KB Output is correct
17 Correct 27 ms 62920 KB Output is correct
18 Correct 28 ms 62856 KB Output is correct
19 Correct 29 ms 62880 KB Output is correct
20 Correct 29 ms 62952 KB Output is correct
21 Correct 27 ms 62916 KB Output is correct
22 Correct 32 ms 62952 KB Output is correct
23 Correct 29 ms 62928 KB Output is correct
24 Correct 27 ms 62864 KB Output is correct
25 Correct 28 ms 62872 KB Output is correct