oj.uz

Submission #579741

# Submission time Handle Problem Language Result Execution time Memory
579741 2022-06-19T17:44:25 Z HeyYouNotYouYou Paths (BOI18_paths) C++14
23 / 100
 3000 ms 24652 KB 
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 300001,INF=1e12;
int n , m , k , x , col[N], prime[6], vis[N];
vector<int>edges[N];
int ans=0;
void dfs(int node , int prod, int cnt){
  //vis[node]=1;
  if(cnt == k){
    return;
  }
  for(auto u:edges[node])
  {
    if(prod%col[u]!=0){
      ans++;
      dfs(u , prod*col[u] , cnt+1);
    }
  }
}
int32_t main()
{
  //freopen("abc.in", "r", stdin);
  cin >> n >> m >> k ;
  prime[1]=2,prime[2]=3,prime[3]=5,prime[4]=7,prime[5]=11;
  for(int i = 1 ; i <= n ; i ++){
    cin >> x;
    col[i] = prime[x];
  }
  for(int i = 0 ; i < m ; i ++)
  {
    int u , v ;
    cin >> u >> v;
    edges[u].push_back(v);
    edges[v].push_back(u);
  }
  for(int i = 1 ; i <= n ; i++)
  {
    if(!vis[i]){
      dfs(i,col[i],1);
    }
  }
  cout<<ans;
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 6 ms 7356 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 6 ms 7360 KB Output is correct
6 Correct 4 ms 7356 KB Output is correct
7 Correct 4 ms 7352 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 620 ms 17404 KB Output is correct
2 Correct 2805 ms 16744 KB Output is correct
3 Correct 379 ms 24652 KB Output is correct
4 Correct 217 ms 19064 KB Output is correct
5 Correct 199 ms 18996 KB Output is correct
6 Execution timed out 3058 ms 21844 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7252 KB Output is correct
2 Correct 5 ms 7252 KB Output is correct
3 Correct 6 ms 7356 KB Output is correct
4 Correct 4 ms 7252 KB Output is correct
5 Correct 6 ms 7360 KB Output is correct
6 Correct 4 ms 7356 KB Output is correct
7 Correct 4 ms 7352 KB Output is correct
8 Correct 4 ms 7252 KB Output is correct
9 Correct 4 ms 7252 KB Output is correct
10 Correct 4 ms 7252 KB Output is correct
11 Correct 620 ms 17404 KB Output is correct
12 Correct 2805 ms 16744 KB Output is correct
13 Correct 379 ms 24652 KB Output is correct
14 Correct 217 ms 19064 KB Output is correct
15 Correct 199 ms 18996 KB Output is correct
16 Execution timed out 3058 ms 21844 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7252 KB Output is correct
2 Execution timed out 3064 ms 10216 KB Time limit exceeded
3 Halted 0 ms 0 KB -