oj.uz

Submission #473510

# Submission time Handle Problem Language Result Execution time Memory
473510 2021-09-15T15:51:06 Z ZaZo_ Paths (BOI18_paths) C++14
100 / 100
 468 ms 100068 KB 
#include <bits/stdc++.h>
#define ZAZO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
int n , m , k;
vector<int>edges[300001];
int cols[300001];
int DP[300001][1<<5];
int DO_WORK(int node , int mask)
{
  if(DP[node][mask]!=-1) return DP[node][mask];
  int mask2 = mask | (1<<(cols[node]));
  DP[node][mask]=1;
  for(auto newnode : edges[node])
  {
    if(!((1<<cols[newnode])&mask2))
    {
      DP[node][mask] += DO_WORK(newnode , mask2);
    }
  }
  return DP[node][mask];
}
int32_t main() {
  ZAZO
  memset(DP,-1,sizeof DP);
  cin >> n >> m >> k ;
  for(int i = 1 ; i <= n ; i++)
    cin>>cols[i],cols[i]--;
  for(int i = 0 ; i < m ; i++)
  {
    int u , v;
    cin >> u >> v;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  int ans=0;
  for(int i = 1 ; i <= n ; i++)
  {
    ans+=DO_WORK(i,0);
  }
  cout<<ans-n<<endl;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82508 KB Output is correct
2 Correct 40 ms 82432 KB Output is correct
3 Correct 39 ms 82432 KB Output is correct
4 Correct 36 ms 82460 KB Output is correct
5 Correct 38 ms 82508 KB Output is correct
6 Correct 37 ms 82452 KB Output is correct
7 Correct 35 ms 82456 KB Output is correct
8 Correct 43 ms 82480 KB Output is correct
9 Correct 35 ms 82408 KB Output is correct
10 Correct 37 ms 82492 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 92520 KB Output is correct
2 Correct 112 ms 91916 KB Output is correct
3 Correct 384 ms 99808 KB Output is correct
4 Correct 157 ms 94236 KB Output is correct
5 Correct 141 ms 94168 KB Output is correct
6 Correct 272 ms 96996 KB Output is correct
7 Correct 429 ms 99388 KB Output is correct
8 Correct 392 ms 100008 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 82508 KB Output is correct
2 Correct 40 ms 82432 KB Output is correct
3 Correct 39 ms 82432 KB Output is correct
4 Correct 36 ms 82460 KB Output is correct
5 Correct 38 ms 82508 KB Output is correct
6 Correct 37 ms 82452 KB Output is correct
7 Correct 35 ms 82456 KB Output is correct
8 Correct 43 ms 82480 KB Output is correct
9 Correct 35 ms 82408 KB Output is correct
10 Correct 37 ms 82492 KB Output is correct
11 Correct 126 ms 92520 KB Output is correct
12 Correct 112 ms 91916 KB Output is correct
13 Correct 384 ms 99808 KB Output is correct
14 Correct 157 ms 94236 KB Output is correct
15 Correct 141 ms 94168 KB Output is correct
16 Correct 272 ms 96996 KB Output is correct
17 Correct 429 ms 99388 KB Output is correct
18 Correct 392 ms 100008 KB Output is correct
19 Correct 126 ms 92552 KB Output is correct
20 Correct 116 ms 91864 KB Output is correct
21 Correct 384 ms 99412 KB Output is correct
22 Correct 199 ms 94188 KB Output is correct
23 Correct 143 ms 94164 KB Output is correct
24 Correct 287 ms 97024 KB Output is correct
25 Correct 408 ms 99348 KB Output is correct
26 Correct 403 ms 100068 KB Output is correct
27 Correct 128 ms 91800 KB Output is correct
28 Correct 195 ms 93924 KB Output is correct
29 Correct 458 ms 99460 KB Output is correct
30 Correct 360 ms 96432 KB Output is correct
31 Correct 427 ms 96520 KB Output is correct
32 Correct 468 ms 99504 KB Output is correct
33 Correct 37 ms 82500 KB Output is correct
34 Correct 37 ms 82380 KB Output is correct
35 Correct 37 ms 82464 KB Output is correct
36 Correct 38 ms 82400 KB Output is correct
37 Correct 38 ms 82408 KB Output is correct
38 Correct 42 ms 82392 KB Output is correct
39 Correct 36 ms 82420 KB Output is correct
40 Correct 37 ms 82472 KB Output is correct
41 Correct 38 ms 82460 KB Output is correct
42 Correct 36 ms 82480 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 82432 KB Output is correct
2 Correct 78 ms 85364 KB Output is correct
3 Correct 62 ms 85424 KB Output is correct
4 Correct 117 ms 88024 KB Output is correct
5 Correct 93 ms 88504 KB Output is correct
6 Correct 158 ms 88260 KB Output is correct
7 Correct 67 ms 85368 KB Output is correct
8 Correct 131 ms 88132 KB Output is correct
9 Correct 99 ms 88512 KB Output is correct
10 Correct 133 ms 88776 KB Output is correct
11 Correct 145 ms 86716 KB Output is correct
12 Correct 104 ms 87472 KB Output is correct
13 Correct 121 ms 86972 KB Output is correct
14 Correct 151 ms 88120 KB Output is correct
15 Correct 136 ms 88220 KB Output is correct
16 Correct 36 ms 82504 KB Output is correct
17 Correct 37 ms 82508 KB Output is correct
18 Correct 37 ms 82500 KB Output is correct
19 Correct 37 ms 82384 KB Output is correct
20 Correct 37 ms 82388 KB Output is correct
21 Correct 36 ms 82500 KB Output is correct
22 Correct 39 ms 82404 KB Output is correct
23 Correct 37 ms 82440 KB Output is correct
24 Correct 38 ms 82376 KB Output is correct
25 Correct 36 ms 82484 KB Output is correct