Submission #778138

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
778138	2023-07-10T06:38:46 Z	NeroZein	Highway Tolls (IOI18_highway)	C++17	6 / 100	1500 ms	15332 KB

highway

#include "highway.h"
#include "bits/stdc++.h"
using namespace std; 
 
int n, m;
vector<int> pe;
vector<int> dep;
vector<int> in_dep;
vector<vector<pair<int,int>>> g; 
 
void Dfs (int v, int p) {
  in_dep[dep[v]] = v; 
  for (auto [u, i] : g[v]) {
    if (u == p) {
      continue;
    }
    pe[u] = i; 
    dep[u] = dep[v] + 1; 
    Dfs(u, v); 
  }
}
 
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n = N;
  g.resize(n); 
  pe.resize(n); 
  dep.resize(n); 
  in_dep.resize(n);
  m = (int) U.size(); 
  for (int i = 0; i < m; ++i) {
    g[U[i]].push_back({V[i], i});
    g[V[i]].push_back({U[i], i});
  }
  Dfs(0, 0); 
  vector<int> w(m, 0); 
  long long dis = ask(w); 
  int depT = dis / A;
  assert(depT != 0); 
  int l = -1, r = m - 1;
  while (l < r) {
    int mid = (l + r + 1) >> 1;
    vector<int> w(m);
    for (int i = 0; i <= mid; ++i) {
      w[i] = true; 
    }
    if (ask(w) > dis) {
      r = mid - 1;
    } else {
      l = mid;
    }
  }
  answer(l + 1, in_dep[l + 1 + depT]);//S, T
}

Subtask #1
0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	208 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	336 KB	Output is incorrect: {s, t} is wrong.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	1636 KB	Output is correct
2	Correct	13 ms	2968 KB	Output is correct
3	Correct	34 ms	4360 KB	Output is correct
4	Correct	58 ms	12624 KB	Output is correct
5	Correct	52 ms	12620 KB	Output is correct
6	Correct	58 ms	12616 KB	Output is correct
7	Correct	86 ms	12632 KB	Output is correct
8	Correct	62 ms	12620 KB	Output is correct
9	Correct	66 ms	12628 KB	Output is correct