oj.uz

Submission #751670

# Submission time Handle Problem Language Result Execution time Memory
751670 2023-06-01T06:58:04 Z bgnbvnbv Paths (BOI18_paths) C++14
100 / 100
 504 ms 188720 KB 
#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=3e5+10;
const ll inf=1e18;
const ll mod=1e9+7;
ll n,m,a[maxN];
vector<ll>g[maxN];
ll dp[maxN][1<<5];
ll k;
vector<ll>vec[maxN][6];
void solve()
{
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++) cin >> a[i],a[i]--;
    for(int i=1;i<=m;i++)
    {
        ll u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    for(int i=1;i<=n;i++)
    {
        dp[i][1<<a[i]]=1;
        for(int j=0;j<(1<<k);j++)
        {
            if(j>>a[i]&1)
            {
                vec[i][__builtin_popcount(j)].pb(j);
            }
        }
    }
    for(int q=2;q<=k;q++)
    {
        for(int i=1;i<=n;i++)
        {
            for(auto j:g[i])
            {
                for(auto vc:vec[i][q])
                {
                    dp[i][vc]+=dp[j][vc-(1<<a[i])];
                }
            }
        }
    }
    ll ans=0;
    for(int j=0;j<(1<<k);j++) for(int i=1;i<=n;i++) ans+=dp[i][j];
    ans-=n;
    cout << ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49620 KB Output is correct
2 Correct 28 ms 49628 KB Output is correct
3 Correct 26 ms 49652 KB Output is correct
4 Correct 25 ms 49620 KB Output is correct
5 Correct 24 ms 49620 KB Output is correct
6 Correct 25 ms 49668 KB Output is correct
7 Correct 25 ms 49620 KB Output is correct
8 Correct 24 ms 49628 KB Output is correct
9 Correct 24 ms 49620 KB Output is correct
10 Correct 25 ms 49596 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 60880 KB Output is correct
2 Correct 81 ms 59324 KB Output is correct
3 Correct 330 ms 169836 KB Output is correct
4 Correct 124 ms 69828 KB Output is correct
5 Correct 119 ms 68892 KB Output is correct
6 Correct 253 ms 132880 KB Output is correct
7 Correct 341 ms 170000 KB Output is correct
8 Correct 387 ms 170272 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 49620 KB Output is correct
2 Correct 28 ms 49628 KB Output is correct
3 Correct 26 ms 49652 KB Output is correct
4 Correct 25 ms 49620 KB Output is correct
5 Correct 24 ms 49620 KB Output is correct
6 Correct 25 ms 49668 KB Output is correct
7 Correct 25 ms 49620 KB Output is correct
8 Correct 24 ms 49628 KB Output is correct
9 Correct 24 ms 49620 KB Output is correct
10 Correct 25 ms 49596 KB Output is correct
11 Correct 88 ms 60880 KB Output is correct
12 Correct 81 ms 59324 KB Output is correct
13 Correct 330 ms 169836 KB Output is correct
14 Correct 124 ms 69828 KB Output is correct
15 Correct 119 ms 68892 KB Output is correct
16 Correct 253 ms 132880 KB Output is correct
17 Correct 341 ms 170000 KB Output is correct
18 Correct 387 ms 170272 KB Output is correct
19 Correct 90 ms 60840 KB Output is correct
20 Correct 73 ms 59260 KB Output is correct
21 Correct 350 ms 169848 KB Output is correct
22 Correct 143 ms 69864 KB Output is correct
23 Correct 141 ms 68952 KB Output is correct
24 Correct 266 ms 132840 KB Output is correct
25 Correct 358 ms 169904 KB Output is correct
26 Correct 377 ms 170096 KB Output is correct
27 Correct 84 ms 59224 KB Output is correct
28 Correct 120 ms 63464 KB Output is correct
29 Correct 500 ms 188716 KB Output is correct
30 Correct 300 ms 123948 KB Output is correct
31 Correct 358 ms 124048 KB Output is correct
32 Correct 504 ms 188720 KB Output is correct
33 Correct 37 ms 49612 KB Output is correct
34 Correct 27 ms 49676 KB Output is correct
35 Correct 26 ms 49572 KB Output is correct
36 Correct 31 ms 49532 KB Output is correct
37 Correct 26 ms 49628 KB Output is correct
38 Correct 29 ms 49632 KB Output is correct
39 Correct 26 ms 49624 KB Output is correct
40 Correct 26 ms 49568 KB Output is correct
41 Correct 27 ms 49520 KB Output is correct
42 Correct 27 ms 49636 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 49620 KB Output is correct
2 Correct 53 ms 52644 KB Output is correct
3 Correct 42 ms 52624 KB Output is correct
4 Correct 112 ms 89516 KB Output is correct
5 Correct 100 ms 90048 KB Output is correct
6 Correct 206 ms 103684 KB Output is correct
7 Correct 45 ms 52652 KB Output is correct
8 Correct 148 ms 95848 KB Output is correct
9 Correct 145 ms 96344 KB Output is correct
10 Correct 141 ms 96056 KB Output is correct
11 Correct 132 ms 77804 KB Output is correct
12 Correct 170 ms 91084 KB Output is correct
13 Correct 126 ms 77936 KB Output is correct
14 Correct 209 ms 103664 KB Output is correct
15 Correct 204 ms 103704 KB Output is correct
16 Correct 26 ms 49612 KB Output is correct
17 Correct 29 ms 49612 KB Output is correct
18 Correct 26 ms 49676 KB Output is correct
19 Correct 29 ms 49620 KB Output is correct
20 Correct 28 ms 49560 KB Output is correct
21 Correct 29 ms 49624 KB Output is correct
22 Correct 29 ms 49624 KB Output is correct
23 Correct 26 ms 49608 KB Output is correct
24 Correct 26 ms 49612 KB Output is correct
25 Correct 27 ms 49620 KB Output is correct