제출 #1016631

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1016631		cadmiumsky	통행료 (IOI18_highway)	C++17	100 / 100	204 ms	17992 KiB

highway

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

#include "highway.h"
#define int ll

const int nmax = 1e5 + 5;
vector<pii> g[nmax];

int N, M;
int Ask(vector<int> a) {
   vector<signed> b;
   for(auto x : a) b.emplace_back(x);
   return ask(b);
}

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void find_pair(signed n__, std::vector<signed> U, std::vector<signed> V, signed A_cost, signed B_cost) {
   N = n__;
   M = sz(U);
   for(int i = 0; i < sz(U); i++) 
      g[U[i]].emplace_back(V[i], i),
      g[V[i]].emplace_back(U[i], i);
   
   int standard_ = Ask(vector<int>(M, 0));
   int lenght = standard_ / A_cost;
   int root = -1, r = N;
   while(root + 1 < r) {
      int cand = (root + r) / 2;
      if(cand >= N) continue;
      vector<int> A(M, 0);
      for(int i = 0; i <= cand; i++)
         for(auto [x, e] : g[i])
            A[e] = 1;
      if(Ask(A) == standard_)
         root = cand;
      else
         r = cand;
   }
   
   root++;
   
   //cerr << root << '\n';

   vector<int> list, p(N, -1);
   vector<int> arriv(N, 0);
   vector<vector<int>> bydist(N, vector<int>());
   queue<int> que;
   que.emplace(root);
   p[root] = root;
   while(!que.empty()) {
      int node = que.front();
      que.pop();
      if(node < root) {
         p[node] = -1;
         continue;
      }
      
      bydist[arriv[node]].emplace_back(node);
      
      list.emplace_back(node);
      shuffle(all(g[node]), rng);
      for(auto [x, e] : g[node]) {
         if(p[x] == -1)
            p[x] = node, que.emplace(x),
            arriv[x] = arriv[node] + 1;
      }
   }
   
   int S = sz(list), l = 0;
   while(l + 1 < S) {
      int cand = (S + l) / 2;
      if(cand < 0) continue;
      vector<int> A(M, 0);
      for(int i = 0; i < root; i++) 
         for(auto [x, e] : g[i])
            A[e] = 1;
      for(int a = cand; a < sz(list); a++)
         for(auto [x, e] : g[list[a]])
            A[e] = 1;
      if(Ask(A) == standard_) S = cand;
      else l = cand;
   }
   
   S--;
   S = list[S];
   
   //cerr << S << '\n';
   
   vector<int> exonerate(N, 0);
   int tmp = S;
   while(tmp != root) exonerate[tmp] = 1, tmp = p[tmp];
   //cerr << '\n';
   
   list = move(bydist[lenght - arriv[S]]);
   
   int T = sz(list); l = 0;
   while(l + 1 < T) {
      int cand = (T + l) / 2;
      if(cand < 0) continue;
      vector<int> A(M, 0);
      for(int i = 0; i < root; i++) 
         for(auto [x, e] : g[i])
            A[e] = 1;
      for(int a = cand; a < sz(list); a++)
         if(!exonerate[list[a]])
            for(auto [x, e] : g[list[a]])
               A[e] = 1;
      if(Ask(A) == standard_) T = cand;
      else l = cand;
   }
   
   T = list[T - 1];
   
   answer(S, T);
   return;
}
#undef int

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