oj.uz

Submission #189111

# Submission time Handle Problem Language Result Execution time Memory
189111 2020-01-13T18:54:35 Z nicolaalexandra Paths (BOI18_paths) C++14
100 / 100
 1053 ms 139540 KB 
#include <bits/stdc++.h>
#define DIM 300010
using namespace std;
vector <int> L[DIM];
long long dp[DIM][50];
int n,m,k,i,j,x,y,nr;
int v[DIM];
int main (){

    cin>>n>>m>>k;
    for (i=1;i<=n;i++){
        cin>>v[i];
        dp[i][(1<<(v[i]-1))] = 1;
    }
    for (i=1;i<=m;i++){
        cin>>x>>y;
        L[x].push_back(y);
        L[y].push_back(x);
    }

    for (nr=2;nr<=k;nr++){
        /// mai adaug o culoare la masca
        for (i=1;i<=n;i++){
            for (auto vecin:L[i]){
                for (int mask=0;mask<(1<<k);mask++){
                    if (!(mask&(1<<(v[i]-1))) && __builtin_popcount(mask) == nr-1)
                        dp[i][mask|(1<<(v[i]-1))] += dp[vecin][mask];

                }}}}

    long long sol = 0;
    for (i=1;i<=n;i++)
        for (int mask=0;mask<(1<<k);mask++)
            sol += dp[i][mask];

    cout<<sol-n;

    return 0;
}

Subtask #1
23.0 / 23.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 330 ms 15848 KB Output is correct
2 Correct 271 ms 13484 KB Output is correct
3 Correct 842 ms 138876 KB Output is correct
4 Correct 423 ms 27100 KB Output is correct
5 Correct 396 ms 27052 KB Output is correct
6 Correct 689 ms 97772 KB Output is correct
7 Correct 843 ms 138888 KB Output is correct
8 Correct 856 ms 139540 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 9 ms 7416 KB Output is correct
3 Correct 9 ms 7416 KB Output is correct
4 Correct 9 ms 7416 KB Output is correct
5 Correct 11 ms 7416 KB Output is correct
6 Correct 8 ms 7416 KB Output is correct
7 Correct 10 ms 7416 KB Output is correct
8 Correct 9 ms 7416 KB Output is correct
9 Correct 2 ms 7416 KB Output is correct
10 Correct 9 ms 7416 KB Output is correct
11 Correct 330 ms 15848 KB Output is correct
12 Correct 271 ms 13484 KB Output is correct
13 Correct 842 ms 138876 KB Output is correct
14 Correct 423 ms 27100 KB Output is correct
15 Correct 396 ms 27052 KB Output is correct
16 Correct 689 ms 97772 KB Output is correct
17 Correct 843 ms 138888 KB Output is correct
18 Correct 856 ms 139540 KB Output is correct
19 Correct 336 ms 15956 KB Output is correct
20 Correct 270 ms 13396 KB Output is correct
21 Correct 879 ms 138916 KB Output is correct
22 Correct 533 ms 27112 KB Output is correct
23 Correct 420 ms 27100 KB Output is correct
24 Correct 694 ms 97628 KB Output is correct
25 Correct 846 ms 139120 KB Output is correct
26 Correct 843 ms 139512 KB Output is correct
27 Correct 327 ms 13432 KB Output is correct
28 Correct 413 ms 17856 KB Output is correct
29 Correct 1039 ms 138872 KB Output is correct
30 Correct 823 ms 76780 KB Output is correct
31 Correct 791 ms 76744 KB Output is correct
32 Correct 1053 ms 138872 KB Output is correct
33 Correct 8 ms 7416 KB Output is correct
34 Correct 9 ms 7416 KB Output is correct
35 Correct 9 ms 7416 KB Output is correct
36 Correct 9 ms 7416 KB Output is correct
37 Correct 8 ms 7416 KB Output is correct
38 Correct 9 ms 7416 KB Output is correct
39 Correct 9 ms 7416 KB Output is correct
40 Correct 9 ms 7420 KB Output is correct
41 Correct 13 ms 7416 KB Output is correct
42 Correct 2 ms 7416 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 7416 KB Output is correct
2 Correct 161 ms 9592 KB Output is correct
3 Correct 94 ms 9464 KB Output is correct
4 Correct 258 ms 51060 KB Output is correct
5 Correct 252 ms 51852 KB Output is correct
6 Correct 450 ms 51052 KB Output is correct
7 Correct 115 ms 9464 KB Output is correct
8 Correct 330 ms 51212 KB Output is correct
9 Correct 291 ms 51976 KB Output is correct
10 Correct 307 ms 52024 KB Output is correct
11 Correct 336 ms 30324 KB Output is correct
12 Correct 350 ms 41180 KB Output is correct
13 Correct 393 ms 30492 KB Output is correct
14 Correct 504 ms 51160 KB Output is correct
15 Correct 470 ms 51300 KB Output is correct
16 Correct 9 ms 7416 KB Output is correct
17 Correct 9 ms 7416 KB Output is correct
18 Correct 1 ms 7416 KB Output is correct
19 Correct 9 ms 7416 KB Output is correct
20 Correct 13 ms 7416 KB Output is correct
21 Correct 9 ms 7416 KB Output is correct
22 Correct 19 ms 7416 KB Output is correct
23 Correct 13 ms 7416 KB Output is correct
24 Correct 9 ms 7416 KB Output is correct
25 Correct 7 ms 7416 KB Output is correct