Submission #582135

#	Time	Username	Problem	Language	Result	Execution time	Memory
582135		Vanilla	Highway Tolls (IOI18_highway)	C++17	0 / 100	263 ms	262144 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
typedef long long int64;
using namespace std;
const int maxn = 9e4 + 2;
const int maxm = 13e4 + 2;
vector <int> ad [maxn];
vector <int> ord;
int N, M;

// int64 query (int x) {
//   vector <int> w (M, 0);
//   for (int i = 0; i <= x; i++){
//     w[i] = 1;
//   }
//   return ask(w);
// }

void dfs (int u, int p) {
  ord.push_back(u);
  for (int v: ad[u]) {
    if (v == p) continue;
    dfs(v, u);
  }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b) {
  int m = u.size();
  N = n;
  M = m;
  for (int i = 0; i < m; i++){
    ad[u[i]].push_back(v[i]);
    ad[v[i]].push_back(u[i]);
  }
  vector <int> w (m, 1);
  int64 tg = ask(w);
  int len = tg / b;
  dfs(0, -1);
  answer(0, ord[len]);
  // int l = 0, r = m - 1, rs = -1;
  // while (l <= r) {
  //   int mid = (l + r) / 2;
  //   cout << mid << " " << query(mid) << "\n";
  //   if (query(mid) >= tg) {
  //     rs = mid;
  //     r = mid - 1;
  //   }
  //   else {
  //     l = mid + 1;
  //   }
  // }
  // answer(0, rs);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31