Submission #1016334

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016334		cadmiumsky	Highway Tolls (IOI18_highway)	C++17	90 / 100	197 ms	15132 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);
}

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_ ;
   int root = -1;
   
   for(int step = 16; step >= 0; step--) {
      if(root + (1 << step) >= N) continue;
      int cand = root + (1 << step);
      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;
   }
   
   root++;
   
   //cerr << root << '\n';

   vector<int> list, p(N, -1);
   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;
      }
      list.emplace_back(node);
      for(auto [x, e] : g[node]) {
         if(p[x] == -1)
            p[x] = node, que.emplace(x);
      }
   }
   
   int S = sz(list);
   for(int i = 16; i >= 0; i--) {
      if(S - (1 << i) < 0) continue;
      int cand = S - (1 << i);
      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 -= (1 << i);
   }
   
   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';
   
   int T = sz(list);
   for(int i = 16; i >= 0; i--) {
      if(T - (1 << i) < 0) continue;
      int cand = T - (1 << i);
      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 -= (1 << i);
   }
   
   T = list[T - 1];
   //cerr << T << '\n';
   
   answer(S, T);
   return;
}
#undef int

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:34:8: warning: unused variable 'lenght' [-Wunused-variable]
   34 |    int lenght = standard_ ;
      |        ^~~~~~

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