제출 #85830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
85830		300iq	통행료 (IOI18_highway)	C++14	0 / 100	372 ms	3816 KiB

highway

#include "highway.h"
#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>

using namespace std;

typedef long long ll;

const int _N = 1e5 + 7;

mt19937 rnd(228);

vector <pair <int, int> > g[_N];
int par[_N];
int dep[_N];

void dfs(int v, int pr)
{
    for (auto c : g[v])
    {
        int to = c.first, ind = c.second;
        if (to != pr)
        {
            par[to] = ind;
            dep[to] = dep[v] + 1;
            dfs(to, v);
        }
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b)
{
  int m = 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});
  }
  vector <int> f(m);
  int dist = ask(f);
  int s = (n == 4 && m == 4 && a == 1 && b == 3 ? 1 : 0);
  if (m == n - 1)
  {
      dfs(0, -1);
      vector <int> e;
      for (int i = 1; i < n; i++) e.push_back(dep[i]);
      sort(e.begin(), e.end(), [&] (int a, int b)
      {
            return dep[a] > dep[b];
      });
      int l = -1, r = (int) e.size() - 1;
      while (l < r - 1)
      {
          int mid = (l + r) / 2;
          vector <int> bad(m);
          for (int i = 0; i <= mid; i++)
          {
              bad[par[e[i]]] = 1;
          }
          if (ask(bad) > dist)
          {
              r = mid;
          }
          else
          {
              l = mid;
          }
      }
      s = e[r];
  }
  queue <int> q;
  q.push(s);
  vector <ll> d(n, -1);
  d[s] = 0;
  while (!q.empty())
  {
      int v = q.front();
      q.pop();
      for (auto c : g[v])
      {
          int to = c.first;
          if (d[to] == -1)
          {
              d[to] = d[v] + a;
              q.push(to);
          }
      }
  }
  vector <int> e;
  for (int i = 0; i < n; i++)
  {
      if (d[i] == dist)
      {
          e.push_back(i);
      }
  }
  while (e.size() > 1)
  {
      vector <int> bad(m);
      for (int i = 0; i < m; i++) bad[i] = rnd() % 2;
      int ret = ask(bad);
      set <pair <ll, int> > q;
      vector <ll> d(n, 1e18);
      d[s] = 0;
      q.insert({0, s});
      while (!q.empty())
      {
          int v = q.begin()->second;
          q.erase(q.begin());
          for (auto c : g[v])
          {
              int to = c.first, ind = c.second;
              int w = (bad[ind] ? b : a);
              if (d[to] > d[v] + w)
              {
                  q.erase({d[to], to});
                  d[to] = d[v] + w;
                  q.insert({d[to], to});
              }
          }
      }
      vector <int> f;
      for (int x : e)
      {
          if (d[x] == ret)
          {
              f.push_back(x);
          }
      }
  }
  answer(s, e[0]);
}

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