oj.uz

Submission #987697

# Submission time Handle Problem Language Result Execution time Memory
987697 2024-05-23T11:28:52 Z Tsagana Race (IOI11_race) C++14
0 / 100
 3 ms 8540 KB 
#include "race.h"

#include<bits/stdc++.h>

#define all(x) x.begin(), x.end()
#define pq priority_queue
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define F first
#define S second

using namespace std;

vector<pair<int, int>> adj[200001];
int mn = 2e9;
void dfs(int s, int val, int cnt, int key, int vis[]) {
  if (val == key) {mn = min(mn, cnt); return ;}

  for (auto i: adj[s]) {
    if (vis[i.F] || val + i.S > key) continue ;
    vis[i.F] = 1; dfs(i.F, val + i.S, cnt + 1, key, vis); vis[i.F] = 0;
  }
}

int best_path(int N, int K, int H[][2], int L[]) {
  for (int i = 0; i < N-1; i++) {
    adj[H[i][0]].pb({H[i][1], L[i]});
    adj[H[i][1]].pb({H[i][0], L[i]});
  }
  int a[N] = {0};
  for (int i = 0; i < N; i++) dfs(i, 0, 0, K, a);
  return mn;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Incorrect 2 ms 8540 KB Output isn't correct
4 Halted 0 ms 0 KB -