Submission #414627

#	Time	Username	Problem	Language	Result	Execution time	Memory
414627		schse	Highway Tolls (IOI18_highway)	C++17	100 / 100	279 ms	11624 KiB

highway

#include "highway.h"
#ifndef EVAL
#include "grader.cpp"
#endif
#include <cassert>
#include <bits/stdc++.h>
using namespace std;

struct node
{
  vector<pair<int, int>> edges; // to number;
  bool been = false;
  int depth;
};

vector<node> g;
std::vector<int> w;
long long lastanswer = 0;
/*
vector<int> maketree(int root, vector<int> U, vector<int> V) //returns translation layer
{

  for (int i = 0; i < g.size(); i++)
    g[i].been = false;
  vector<int> trans;
  queue<pair<int, int>> q; // node depth;
  q.push({root, 0});
  g[root].been = true;
  while (!q.empty())
  {
    auto p = q.front();
    q.pop();
    g[p.first].depth = p.second;
    for (auto i : g[p.first].edges)
    {
      if (g[i.first].been)
        continue;
      g[i.first].been = true;
      trans.push_back(i.second);
      q.push({i.first, p.second + 1});
    }
  }
  return trans;
}
*/
pair<vector<int>, vector<int>> maketwotrees(int rootU, int rootV, int edgeon)
{
  for (int i = 0; i < g.size(); i++)
    g[i].been = false;
  vector<int> rootedinU;
  vector<int> rootedinV;
  rootedinV.push_back(edgeon);
  rootedinU.push_back(edgeon);
  queue<tuple<int, int, bool>> q; // node depth;
  q.push({rootU, 0, false});
  q.push({rootV, 0, true});
  g[rootU].been = true;
  g[rootV].been = true;
  while (!q.empty())
  {
    auto [to, depth, from] = q.front();
    q.pop();
    g[to].depth = depth;
    for (auto i : g[to].edges)
    {
      if (g[i.first].been)
        continue;
      g[i.first].been = true;
      (from ? rootedinV : rootedinU).push_back(i.second);
      q.push({i.first, depth + 1, from});
    }
  }
  return {rootedinU, rootedinV};
}

int binarysearnew(vector<int> translation, vector<int> inactive)
{
  // trans translation
  int b = 0;
  int e = translation.size();
  while (b + 1 != e)
  {
    fill(w.begin(), w.end(), 1);
    for (int x : inactive)
      w[x] = 0;
    for (int x : translation)
      w[x] = 0;
    for (int i = (b + e) / 2; i < e; i++)
      w[translation[i]] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
      b = (b + e) / 2;
    else
      e = (b + e) / 2;
  }
  return translation[b];
}
/*
int binarysear(vector<int> translation)
{
  // trans translation
  int b = 0;
  int e = translation.size();
  while (b + 1 != e)
  {
    fill(w.begin(), w.end(), 1);
    for (int x : translation)
      w[x] = 0;

    for (int i = (b + e) / 2; i < e; i++)
      w[translation[i]] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
      b = (b + e) / 2;
    else
      e = (b + e) / 2;
  }
  return translation[b];
}
*/
int binarysearPoints()
{
  int b = 0;
  int e = w.size();
  fill(w.begin(), w.end(), 0);
  while (b + 1 != e)
  {
    for (int i = (b + e) / 2; i < e; i++)
      w[i] = 1;
    long long tmp = ask(w);
    if (tmp != lastanswer)
    {
      for (int i = (b + e) / 2; i < e; i++)
        w[i] = 0;
      b = (b + e) / 2;
    }
    else
      e = (b + e) / 2;
  }
  return b;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B)
{
  int M = U.size();
  vector<int> inorderbfs(M);
  g.resize(N);
  w.resize(M);
  for (int i = 0; i < U.size(); i++) // rebuild graph
  {
    g[U[i]].edges.push_back({V[i], i});
    g[V[i]].edges.push_back({U[i], i});
  }

  fill(w.begin(), w.end(), 0);
  lastanswer = ask(w);

  //Punkt auf Pfad
  int edgeonpath = binarysearPoints();

  auto [Utranslation, Vtranslation] = maketwotrees(U[edgeonpath], V[edgeonpath],edgeonpath); // rooted in

  // 1.Endpunkt
  //inorderbfs = maketree(edgeinpath, U, V);
  int endpointa, endpointb;
  if (!Utranslation.empty())
  {
    int tmp = binarysearnew(Utranslation, Vtranslation);
    endpointa = V[tmp];
    if (g[U[tmp]].depth >= g[V[tmp]].depth)
      endpointa = U[tmp];
    assert(endpointa != -1);
  }
  else
    endpointa = V[edgeonpath];

  //2. Endpunkt
  //inorderbfs = maketree(endpointa, U, V);
  if (!Vtranslation.empty())
  {
    int tmp = binarysearnew(Vtranslation, Utranslation);
    //tmp = binarysear(inorderbfs);
    endpointb = U[tmp];
    if (g[V[tmp]].depth >= g[U[tmp]].depth)
      endpointb = V[tmp];
  }
  else
    endpointa = U[edgeonpath];

  answer(endpointa, endpointb);
}

Compilation message (stderr)

highway.cpp: In function 'std::pair<std::vector<int>, std::vector<int> > maketwotrees(int, int, int)':
highway.cpp:48:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for (int i = 0; i < g.size(); i++)
      |                   ~~^~~~~~~~~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:149:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |   for (int i = 0; i < U.size(); i++) // rebuild graph
      |                   ~~^~~~~~~~~~
highway.cpp:190:9: warning: 'endpointb' may be used uninitialized in this function [-Wmaybe-uninitialized]
  190 |   answer(endpointa, endpointb);
      |   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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