oj.uz

Submission #488536

# Submission time Handle Problem Language Result Execution time Memory
488536 2021-11-19T13:50:20 Z FatihSolak Paths (BOI18_paths) C++17
100 / 100
 381 ms 93028 KB 
#include <bits/stdc++.h>
#define N 300005
#define K 5
using namespace std;
int n,m,k;
int arr[N];
long long dp[N][(1<<K)];
vector<int > adj[N];
long long f(int v,int mask){
    if( (mask & (1<<arr[v])) == 0)return 0;
    if(mask == (1<<arr[v]))return 1;
    if(dp[v][mask] != -1)return dp[v][mask];
    dp[v][mask] = 0;
    for(auto u:adj[v]){
        dp[v][mask] += f(u,mask^(1<<arr[v]));
    }
    return dp[v][mask];
}
void solve(){
    for(int i=0;i<N;i++){
        for(int j=0;j<(1<<K);j++){
            dp[i][j] = -1;
        }
    }
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        cin >> arr[i];
        arr[i]--;
    }
    for(int i=0;i<m;i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    long long ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<(1<<k);j++){
            ans += f(i,j);
        }
    }
    cout << ans - n;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 82408 KB Output is correct
2 Correct 35 ms 82384 KB Output is correct
3 Correct 34 ms 82500 KB Output is correct
4 Correct 34 ms 82460 KB Output is correct
5 Correct 35 ms 82480 KB Output is correct
6 Correct 40 ms 82444 KB Output is correct
7 Correct 35 ms 82496 KB Output is correct
8 Correct 38 ms 82460 KB Output is correct
9 Correct 37 ms 82508 KB Output is correct
10 Correct 35 ms 82508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 87148 KB Output is correct
2 Correct 95 ms 87088 KB Output is correct
3 Correct 307 ms 92648 KB Output is correct
4 Correct 114 ms 87304 KB Output is correct
5 Correct 106 ms 87368 KB Output is correct
6 Correct 224 ms 90696 KB Output is correct
7 Correct 306 ms 92376 KB Output is correct
8 Correct 313 ms 92952 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 82408 KB Output is correct
2 Correct 35 ms 82384 KB Output is correct
3 Correct 34 ms 82500 KB Output is correct
4 Correct 34 ms 82460 KB Output is correct
5 Correct 35 ms 82480 KB Output is correct
6 Correct 40 ms 82444 KB Output is correct
7 Correct 35 ms 82496 KB Output is correct
8 Correct 38 ms 82460 KB Output is correct
9 Correct 37 ms 82508 KB Output is correct
10 Correct 35 ms 82508 KB Output is correct
11 Correct 101 ms 87148 KB Output is correct
12 Correct 95 ms 87088 KB Output is correct
13 Correct 307 ms 92648 KB Output is correct
14 Correct 114 ms 87304 KB Output is correct
15 Correct 106 ms 87368 KB Output is correct
16 Correct 224 ms 90696 KB Output is correct
17 Correct 306 ms 92376 KB Output is correct
18 Correct 313 ms 92952 KB Output is correct
19 Correct 100 ms 86464 KB Output is correct
20 Correct 87 ms 86332 KB Output is correct
21 Correct 322 ms 92276 KB Output is correct
22 Correct 116 ms 87276 KB Output is correct
23 Correct 109 ms 87364 KB Output is correct
24 Correct 221 ms 90692 KB Output is correct
25 Correct 304 ms 92372 KB Output is correct
26 Correct 302 ms 93028 KB Output is correct
27 Correct 108 ms 86336 KB Output is correct
28 Correct 131 ms 87148 KB Output is correct
29 Correct 375 ms 92372 KB Output is correct
30 Correct 282 ms 89272 KB Output is correct
31 Correct 291 ms 89280 KB Output is correct
32 Correct 381 ms 92372 KB Output is correct
33 Correct 38 ms 82372 KB Output is correct
34 Correct 36 ms 82464 KB Output is correct
35 Correct 35 ms 82508 KB Output is correct
36 Correct 35 ms 82564 KB Output is correct
37 Correct 35 ms 82436 KB Output is correct
38 Correct 35 ms 82508 KB Output is correct
39 Correct 35 ms 82456 KB Output is correct
40 Correct 35 ms 82508 KB Output is correct
41 Correct 36 ms 82456 KB Output is correct
42 Correct 35 ms 82456 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 82488 KB Output is correct
2 Correct 73 ms 84248 KB Output is correct
3 Correct 53 ms 84236 KB Output is correct
4 Correct 100 ms 86696 KB Output is correct
5 Correct 81 ms 87388 KB Output is correct
6 Correct 157 ms 86724 KB Output is correct
7 Correct 60 ms 84356 KB Output is correct
8 Correct 124 ms 86844 KB Output is correct
9 Correct 98 ms 87496 KB Output is correct
10 Correct 105 ms 87484 KB Output is correct
11 Correct 120 ms 85500 KB Output is correct
12 Correct 128 ms 86640 KB Output is correct
13 Correct 125 ms 85772 KB Output is correct
14 Correct 158 ms 86736 KB Output is correct
15 Correct 148 ms 86836 KB Output is correct
16 Correct 36 ms 82476 KB Output is correct
17 Correct 35 ms 82392 KB Output is correct
18 Correct 36 ms 82468 KB Output is correct
19 Correct 41 ms 82428 KB Output is correct
20 Correct 35 ms 82508 KB Output is correct
21 Correct 35 ms 82508 KB Output is correct
22 Correct 35 ms 82380 KB Output is correct
23 Correct 37 ms 82372 KB Output is correct
24 Correct 35 ms 82420 KB Output is correct
25 Correct 35 ms 82508 KB Output is correct