Submission #1368986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1368986		altern23	Highway Tolls (IOI18_highway)	C++20	69 / 100	58 ms	11716 KiB

highway

#include "highway.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
      // find a set of vertices which partitions A and B into different groups
      ll M = U.size();

      if (M == N-1) {
            vector <pair<ll, ll>> adj[N+5];
            for (int i=0; i<M; i++) {
                  adj[U[i]].push_back({V[i], i}), adj[V[i]].push_back({U[i], i});
            }

            vector <int> W(M), dist(N, 1e9), par(N);

            ll z = ask(W)/A;

            queue <ll> q;
            dist[0] = 0;
            q.push(0);
            
            vector <ll> v;

            while (!q.empty()) {
                  auto idx = q.front(); q.pop();
                  v.push_back(idx);
                  for (auto [i, j] : adj[idx]) {
                        if (dist[i]>dist[idx]+1) {
                              dist[i] = dist[idx]+1;
                              par[i] = j;
                              q.push(i);
                        }
                  }
            }

            sort(v.begin(), v.end(), [&](ll a, ll b) {
                  return dist[a]>dist[b];
            });

            ll lf = 0, rg = (ll)v.size()-1, S = -1, T = -1;
            ll cur = -1;
            
            while (lf<=rg) {
                  ll mid = (lf+rg)/2;
                  while (cur+1<=mid) {
                        cur++;
                        W[par[v[cur]]] = 1;
                  }
                  while (cur>mid) {
                        W[par[v[cur]]] = 0;
                        cur--;
                  }
                  if (ask(W) != z*A) {
                        S = v[mid];
                        rg = mid-1;
                  }
                  else lf = mid+1;
            }
            
            for (int i=0; i<N; i++) dist[i] = 1e9;
            for (int i=0; i<M; i++) W[i] = 0;

            dist[S] = 0;
            q.push(S);
            
            v.clear();
            while (!q.empty()) {
                  auto idx = q.front(); q.pop();
                  if (dist[idx] == z) {
                        v.push_back(idx);
                        continue;
                  }
                  for (auto [i, j] : adj[idx]) {
                        if (dist[i]>dist[idx]+1) {
                              dist[i] = dist[idx]+1;
                              par[i] = j;
                              q.push(i);
                        }
                  }
            }

            lf = 0, rg = (ll)v.size()-1;
            cur = -1;
            
            while (lf<=rg) {
                  ll mid = (lf+rg)/2;
                  while (cur+1<=mid) {
                        cur++;
                        W[par[v[cur]]] = 1;
                  }
                  while (cur>mid) {
                        W[par[v[cur]]] = 0;
                        cur--;
                  }
                  if (ask(W) != z*A) {
                        T = v[mid];
                        rg = mid-1;
                  }
                  else lf = mid+1;
            }

            answer(S, T);
            return;
      }

      vector <ll> tmp(N), gr(N);
      vector <int> W(M);

      ll z = 0;

      auto check = [&]() {
            return ask(W)%2;
      };

      for (int i=0; i<17; i++) {
            for (int j=0; j<N; j++) {
                  tmp[j] = (j>>i&1);
            }
            for (int j=0; j<M; j++) {
                  W[j] = !(tmp[U[j]] != tmp[V[j]]);
            }
            if (check()) {
                  z += (1LL<<i);
                  gr = tmp;
            }
      }

      vector <int> x, y;
      for (int i=0; i<N; i++) {
            if (gr[i]) x.push_back(i);
            else y.push_back(i);
      }

      ll K = x.size();

      ll lf = 0, rg = K-1, S = -1;
      while (lf<=rg) {
            ll mid = (lf+rg)/2;
            for (int j=0; j<N; j++) {
                  tmp[j] = gr[j];
                  if (gr[j] && j>x[mid]) tmp[j] = 0;
            }
            for (int j=0; j<M; j++) {
                  W[j] = !(tmp[U[j]] != tmp[V[j]]);
            }
            if (check()) {
                  S = x[mid];
                  rg = mid-1;
            }
            else lf = mid+1;
      }

      answer(S, S^z);
}

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