답안 #864393

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
864393	2023-10-22T17:22:50 Z	computerbox	경주 (Race) (IOI11_race)	C++14	0 / 100	7 ms	27736 KB

race

#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;
}

Subtask #1

0 / 9.0

#	결과	실행 시간	메모리	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	-

Subtask #2

0 / 12.0

#	결과	실행 시간	메모리	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	-

Subtask #3

0 / 22.0

#	결과	실행 시간	메모리	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	-

Subtask #4

0 / 57.0

#	결과	실행 시간	메모리	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	-