| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 864393 |
2023-10-22T17:22:50 Z |
computerbox |
Race (IOI11_race) |
C++14 |
|
7 ms |
27736 KB |
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int> >adj[1000010];
int ans = INT_MAX;
vector<long long>preff;
void dfs(int v, int p, int k)
{
long long sum = preff.back();
if(sum == k)
{
ans = min(ans, (int)preff.size() - 1);
}
if(sum > k)
{
int need = sum - k;
int indx = lower_bound(preff.begin(), preff.end(), need) - preff.begin();
if(preff[indx] == need)
{
ans = min(ans, (int)preff.size() - indx - 1);
}
}
for(auto to: adj[v])
{
if(to.first == p)continue;
preff.push_back(preff.back() + to.second);
dfs(to.first, v, k);
}
preff.pop_back();
}
int best_path(int N, int K, int H[][2], int L[])
{
for(int i = 0; i < N - 1; i++)
{
adj[H[i][0]].push_back({H[i][1], L[i]});
adj[H[i][1]].push_back({H[i][0], L[i]});
}
preff.push_back(0);
dfs(0, 0, K);
if(ans == INT_MAX)return -1;
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
27560 KB |
Output is correct |
| 4 |
Correct |
5 ms |
27736 KB |
Output is correct |
| 5 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 7 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 8 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 9 |
Correct |
5 ms |
27564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 11 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 12 |
Correct |
6 ms |
27580 KB |
Output is correct |
| 13 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 14 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 15 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 16 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 17 |
Incorrect |
5 ms |
27484 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
27560 KB |
Output is correct |
| 4 |
Correct |
5 ms |
27736 KB |
Output is correct |
| 5 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 7 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 8 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 9 |
Correct |
5 ms |
27564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 11 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 12 |
Correct |
6 ms |
27580 KB |
Output is correct |
| 13 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 14 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 15 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 16 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 17 |
Incorrect |
5 ms |
27484 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
27560 KB |
Output is correct |
| 4 |
Correct |
5 ms |
27736 KB |
Output is correct |
| 5 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 7 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 8 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 9 |
Correct |
5 ms |
27564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 11 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 12 |
Correct |
6 ms |
27580 KB |
Output is correct |
| 13 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 14 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 15 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 16 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 17 |
Incorrect |
5 ms |
27484 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
27484 KB |
Output is correct |
| 2 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 3 |
Correct |
5 ms |
27560 KB |
Output is correct |
| 4 |
Correct |
5 ms |
27736 KB |
Output is correct |
| 5 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 6 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 7 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 8 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 9 |
Correct |
5 ms |
27564 KB |
Output is correct |
| 10 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 11 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 12 |
Correct |
6 ms |
27580 KB |
Output is correct |
| 13 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 14 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 15 |
Correct |
5 ms |
27484 KB |
Output is correct |
| 16 |
Correct |
6 ms |
27484 KB |
Output is correct |
| 17 |
Incorrect |
5 ms |
27484 KB |
Output isn't correct |
| 18 |
Halted |
0 ms |
0 KB |
- |
