Submission #829351

#	Time	Username	Problem	Language	Result	Execution time	Memory
829351		radaiosm7	Highway Tolls (IOI18_highway)	C++17	0 / 100	210 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;
vector<pair<int, int> > adj[90005];
long long a, b, quer, we;
int p[90005];
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 dfs_ch(int x, int p=-1) {
  sub[x] = 1;

  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    dfs_ch(y.X, x);
    sub[x] += sub[y.X];
  }
}

void find_centroid(int x, int p=-1) {
  for (auto y : adj[x]) {
    if (y.X == p || dontUse[y.Y]) continue;
    
    if (sub[y.X] >= sub[x]/2) {
      centroid = make_pair(make_pair(x, y.X), y.Y);
      find_centroid(y.X, x);
    }
  }
}

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

    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+n, 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 = 0;

  do {
    centroid = make_pair(make_pair(st, adj[st][0].X), adj[st][0].Y);
    dfs_ch(st);
    find_centroid(st);
    dontUse[centroid.Y] = true;

    vector<int> w(m, 0);
    w[centroid.Y] = 1;
    quer = ask(w);

    if (quer > we) {
      cont = false;
      roots = centroid.X;

      marked.clear();
      mark(roots.X);
      vector<int> w(m, 0);
      for (auto v : marked) w[v] = 1;
      quer = ask(w);

      dist.X = (int)((quer-we)/(b-a));
      dist.Y = tot-dist.X-1;
    }

    else {
      marked.clear();
      mark(centroid.X.X);
      vector<int> w(m, 0);
      for (auto v : marked) w[v] = 1;

      quer = ask(w);
      if (quer > we) st = centroid.X.X;
      else st = centroid.X.Y;
    }
  } while (cont);

  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: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31