Submission #1326664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1326664		SmuggingSpun	Highway Tolls (IOI18_highway)	C++20	100 / 100	128 ms	15200 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lim = 9e4 + 5;
int n, m, a, b;
vector<int>u, v, g[lim];
namespace sub1234{
  void solve(){
    vector<int>pie(n), h(n);
    function<void(int)>dfs;
    dfs = [&] (int s){
      for(int& i : g[s]){
        if(i != pie[s]){
          int d = u[i] ^ v[i] ^ s;
          pie[d] = i;
          h[d] = h[s] + 1;
          dfs(d);
        }
      }
    };
    ll init = ask(vector<int>(m, 0));
    auto work = [&] (int start){
      fill(pie.begin(), pie.end(), -1);
      h[start] = 0;
      dfs(start);
      vector<int>p(n);
      iota(p.begin(), p.end(), 0);
      sort(p.begin(), p.end(), [&] (int i, int j){
        return h[i] > h[j];
      });
      int low = 0, high = n - 2, ans;
      while(low <= high){
        int mid = (low + high) >> 1;
        vector<int>w(m, 0);
        for(int i = 0; i <= mid; i++){
          w[pie[p[i]]] = 1;
        }
        if(ask(w) > init){
          high = (ans = mid) - 1;
        }
        else{
          low = mid + 1;
        }
      }
      return p[ans];
    };
    int s = work(0);
    answer(s, work(s));
  }
}
namespace sub56{
  vector<int>tree[lim];
  void solve(){
    ll init = ask(vector<int>(m, 0));
    int low = 0, high = n - 1, root;
    while(low <= high){
      int mid = (low + high) >> 1;
      vector<int>w(m, 0);
      for(int i = 0; i <= mid; i++){
        for(int& j : g[i]){
          w[j] = 1;
        }
      }
      if(ask(w) > init){
        high = (root = mid) - 1;
      }
      else{
        low = mid + 1;
      }
    }
    vector<bool>vis(n, false);
    queue<int>q;
    q.push(root);
    vis[root] = true;
    while(!q.empty()){
      int s = q.front();
      q.pop();
      for(int& i : g[s]){
        int d = u[i] ^ v[i] ^ s;
        if(!vis[d]){
          tree[s].push_back(i);
          tree[d].push_back(i);
          vis[d] = true;
          q.push(d);
        }
      }
    }
    vector<int>pie(n), h(n);
    function<void(int)>dfs;
    dfs = [&] (int s){
      for(int& i : tree[s]){
        if(i != pie[s]){
          int d = u[i] ^ v[i] ^ s;
          pie[d] = i;
          h[d] = h[s] + 1;
          dfs(d);
        }
      }
    };
    int dst = init / a, s;
    auto work = [&] (int start, bool first_start){
      vector<int>pre_h;
      if(!first_start){
        pre_h = h;
      }
      fill(pie.begin(), pie.end(), -1);
      h[start] = 0;
      dfs(start);
      vector<int>p;
      for(int i = root; i < n; i++){
        if(i == start){
          continue;
        }
        if(first_start){
          if(h[i] >= (dst >> 1)){
            p.push_back(i);
          }
        }
        else if(h[i] == dst && pre_h[i] == dst - pre_h[s]){
          p.push_back(i);
        }
      }
      sort(p.begin(), p.end(), [&] (int i, int j){
        return h[i] > h[j];
      });
      int low = 0, high = int(p.size()) - 1, ans;
      while(low <= high){
        int mid = (low + high) >> 1;
        vector<int>w(m, 0);
        for(int i = 0; i <= mid; i++){
          for(int& j : g[p[i]]){
            w[j] = 1;
          }
        }
        if(ask(w) > init){
          high = (ans = mid) - 1;
        }
        else{
          low = mid + 1;
        }
      }
      return p[ans];
    };
    s = work(root, true);
    answer(s, work(s, false));
  }
}
void find_pair(int _n, vector<int>_u, vector<int>_v, int _a, int _b){
  n = _n;
  swap(u, _u);
  swap(v, _v);
  a = _a;
  b = _b;
  m = u.size();
  for(int i = 0; i < m; i++){
    g[u[i]].push_back(i);
    g[v[i]].push_back(i);
  }
  if(m == n - 1){
    sub1234::solve();
  }
  else{
    sub56::solve();
  }
}

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