Submission #829427

#	Time	Username	Problem	Language	Result	Execution time	Memory
829427		radaiosm7	Highway Tolls (IOI18_highway)	C++17	51 / 100	168 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second
int n, i, m, st, qi, tot, l, r, nnn;
vector<pair<int, int> > adj[90005];
long long a, b, quer, we;
int sub[90005];
int d[90005];
bool dontUse[90005];
pair<pair<int, int>, int> centroid;
bool cont;
pair<int, int> roots;
pair<int, int> dist;
pair<int, int> ans;
vector<int> marked;
vector<int> vert;

void mark(int x, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    marked.push_back(y.Y);
    mark(y.X, x);
  }
}

void find_dist(int x, int lookFor, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    d[y.X] = d[x]+1;
    
    if (d[y.X] == lookFor) {
      marked.push_back(y.Y);
      vert.push_back(y.X);
    }

    else find_dist(y.X, lookFor, x);
  }
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  m = (int)U.size();
  n = N;
  fill(dontUse, dontUse+m, false);
  a = (long long)A;
  b = (long long)B;

  for (i=0; i < m; ++i) {
    adj[U[i]].push_back(make_pair(V[i], i));
    adj[V[i]].push_back(make_pair(U[i], i));
  }

  vector<int> w(m, 0);
  we = ask(w);
  tot = (int)(we/a);
  cont = true;
  st = rand()%n;
  
  l = 0;
  r = m-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[i] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  roots.X = U[l];
  roots.Y = V[l];
  dontUse[l] = true;

  marked.clear();
  mark(roots.X);
  for (i=0; i < m; ++i) w[i] = 0;
  for (auto v : marked) w[v] = 1;
  quer = ask(w);
  dist.X = (int)((quer-we)/(b-a));
  dist.Y = tot-dist.X-1;

  d[roots.X] = 0;
  marked.clear();
  vert.clear();

  if (dist.X == 0) vert.push_back(roots.X);
  else find_dist(roots.X, dist.X);
  l = 0;
  r = (int)marked.size()-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[marked[i]] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  ans.X = vert[l];

  d[roots.Y] = 0;
  marked.clear();
  vert.clear();

  if (dist.Y == 0) vert.push_back(roots.Y);
  else find_dist(roots.Y, dist.Y);
  l = 0;
  r = (int)marked.size()-1;

  while (l < r) {
    int mid = (l+r)/2;
    vector<int> w(m, 0);
    for (i=0; i <= mid; ++i) w[marked[i]] = 1;
    quer = ask(w);
    if (quer > we) r = mid;
    else l = mid+1;
  }

  ans.Y = vert[l];
  answer(ans.X, ans.Y);
}

/*
12 11 63 8242 2 11           
0 1
1 2
1 3
3 4
4 5
0 6
6 7
7 8
8 9
8 10
7 11
*/

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