제출 #1038750

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1038750		huutuan	통행료 (IOI18_highway)	C++14	51 / 100	104 ms	13752 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

void find_pair(int32_t N, vector<int32_t> U, vector<int32_t> V, int32_t A, int32_t B) {
   vector<vector<int>> g(N);
   for (int i=0; i<N-1; ++i) g[U[i]].push_back(i), g[V[i]].push_back(i);
   vector<pair<int, int>> order;
   vector<int32_t> a(N-1);
   int len=ask(a)/A;
   auto dfs=[&](auto &&self, int u, int p) -> void {
      for (int i:g[u]) if (i!=p){
         int v=u^U[i]^V[i];
         order.emplace_back(i, v);
         self(self, v, i);
      }
   };
   int S, T;
   {
      order.clear();
      dfs(dfs, 0, -1);
      int l=0, r=N-1;
      while (l<=r){
         int mid=(l+r)>>1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=1;
         if (ask(a)==len*B) r=mid-1;
         else l=mid+1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=0;
      }
      S=order[l].second;
   }
   {
      order.clear();
      dfs(dfs, S, -1);
      int l=0, r=N-1;
      while (l<=r){
         int mid=(l+r)>>1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=1;
         if (ask(a)==len*B) r=mid-1;
         else l=mid+1;
         for (int i=0; i<=mid; ++i) a[order[i].first]=0;
      }
      T=order[l].second;
   }
   answer(S, T);
}

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