oj.uz

Submission #703202

# Submission time Handle Problem Language Result Execution time Memory
703202 2023-02-26T14:26:29 Z beaconmc Paths (BOI18_paths) C++14
100 / 100
 776 ms 100604 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)

ll dp[32][300001];

vector<ll> edges[300001];

vector<ll> colours;

int main(){
  ll n,m,k;
  cin >> n >> m >> k;
  FOR(i,0,n){
    ll temp; cin >> temp;
    colours.push_back(temp-1);
  }
  FOR(i,0,m){
    ll a,b;
    cin >> a >> b;
    a--;b--;
    edges[a].push_back(b);
    edges[b].push_back(a);
  }

  FOR(i,0,32) FOR(j,0,300001) dp[i][j] = 0;
  FOR(i,0,n){
    dp[1<<colours[i]][i] = 1;
  }




  FOR(p,1, 1<<k){
    FOR(i,0,n){
      for (auto&j : edges[i]){
        FOR(q, 1, 1<<k){
          if ((q|(1<<colours[i])) == p && ((q&(1<<colours[i])) == 0)){
            dp[p][i] += dp[q][j];
          }
        }
      }
    }
  }

  ll ans = 0;

  FOR(i,0,1<<k){
    if (i==1 || i==2 || i==4 || i==8 || i==16) continue;
    FOR(j,0,n){
      ans += dp[i][j];
    }
  }
  cout << ans << endl;

}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82380 KB Output is correct
2 Correct 33 ms 82456 KB Output is correct
3 Correct 33 ms 82388 KB Output is correct
4 Correct 33 ms 82376 KB Output is correct
5 Correct 38 ms 82456 KB Output is correct
6 Correct 34 ms 82388 KB Output is correct
7 Correct 34 ms 82408 KB Output is correct
8 Correct 33 ms 82356 KB Output is correct
9 Correct 33 ms 82448 KB Output is correct
10 Correct 33 ms 82448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 202 ms 92500 KB Output is correct
2 Correct 168 ms 91836 KB Output is correct
3 Correct 476 ms 99816 KB Output is correct
4 Correct 261 ms 94156 KB Output is correct
5 Correct 203 ms 94096 KB Output is correct
6 Correct 355 ms 97080 KB Output is correct
7 Correct 445 ms 99716 KB Output is correct
8 Correct 469 ms 100604 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 82380 KB Output is correct
2 Correct 33 ms 82456 KB Output is correct
3 Correct 33 ms 82388 KB Output is correct
4 Correct 33 ms 82376 KB Output is correct
5 Correct 38 ms 82456 KB Output is correct
6 Correct 34 ms 82388 KB Output is correct
7 Correct 34 ms 82408 KB Output is correct
8 Correct 33 ms 82356 KB Output is correct
9 Correct 33 ms 82448 KB Output is correct
10 Correct 33 ms 82448 KB Output is correct
11 Correct 202 ms 92500 KB Output is correct
12 Correct 168 ms 91836 KB Output is correct
13 Correct 476 ms 99816 KB Output is correct
14 Correct 261 ms 94156 KB Output is correct
15 Correct 203 ms 94096 KB Output is correct
16 Correct 355 ms 97080 KB Output is correct
17 Correct 445 ms 99716 KB Output is correct
18 Correct 469 ms 100604 KB Output is correct
19 Correct 202 ms 92476 KB Output is correct
20 Correct 175 ms 91984 KB Output is correct
21 Correct 464 ms 99836 KB Output is correct
22 Correct 213 ms 94140 KB Output is correct
23 Correct 208 ms 94188 KB Output is correct
24 Correct 370 ms 96932 KB Output is correct
25 Correct 461 ms 99924 KB Output is correct
26 Correct 454 ms 100388 KB Output is correct
27 Correct 247 ms 91984 KB Output is correct
28 Correct 275 ms 93900 KB Output is correct
29 Correct 776 ms 99888 KB Output is correct
30 Correct 519 ms 96632 KB Output is correct
31 Correct 521 ms 96428 KB Output is correct
32 Correct 758 ms 99836 KB Output is correct
33 Correct 31 ms 82356 KB Output is correct
34 Correct 32 ms 82440 KB Output is correct
35 Correct 31 ms 82416 KB Output is correct
36 Correct 31 ms 82460 KB Output is correct
37 Correct 31 ms 82372 KB Output is correct
38 Correct 32 ms 82380 KB Output is correct
39 Correct 32 ms 82476 KB Output is correct
40 Correct 32 ms 82400 KB Output is correct
41 Correct 30 ms 82460 KB Output is correct
42 Correct 32 ms 82380 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 82396 KB Output is correct
2 Correct 201 ms 85380 KB Output is correct
3 Correct 77 ms 85308 KB Output is correct
4 Correct 134 ms 88064 KB Output is correct
5 Correct 118 ms 88512 KB Output is correct
6 Correct 417 ms 88132 KB Output is correct
7 Correct 109 ms 85384 KB Output is correct
8 Correct 204 ms 88068 KB Output is correct
9 Correct 172 ms 88524 KB Output is correct
10 Correct 191 ms 88640 KB Output is correct
11 Correct 266 ms 86584 KB Output is correct
12 Correct 294 ms 87404 KB Output is correct
13 Correct 283 ms 87272 KB Output is correct
14 Correct 429 ms 88228 KB Output is correct
15 Correct 425 ms 88120 KB Output is correct
16 Correct 32 ms 82412 KB Output is correct
17 Correct 33 ms 82372 KB Output is correct
18 Correct 33 ms 82380 KB Output is correct
19 Correct 32 ms 82376 KB Output is correct
20 Correct 32 ms 82352 KB Output is correct
21 Correct 32 ms 82376 KB Output is correct
22 Correct 34 ms 82388 KB Output is correct
23 Correct 33 ms 82380 KB Output is correct
24 Correct 33 ms 82432 KB Output is correct
25 Correct 32 ms 82408 KB Output is correct