Submission #601540

#	Time	Username	Problem	Language	Result	Execution time	Memory
601540		jack715	Highway Tolls (IOI18_highway)	C++14	5 / 100	137 ms	15284 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pp pop_back
#define mp make_pair
#define bb back
#define ff first
#define ss second

using namespace std;

vector<vector<pair<int, int> > > adj;
int n, m, cost;

int find(int indx, int par = -1) {
  // cout << indx << '\n';
  int l = 0, r = adj[indx].size()-1;
  for (int i = 0; i < adj[indx].size(); i++) {
    if (adj[indx][i].ff == par) {
      r--;
      swap(adj[indx][i], adj[indx].back());
      break;
    }
  }
  if (r == -1) return indx;
  while (l < r) {
    int mid = (l + r) / 2;
    vector<int> q(m, 0);
    for (int i = l; i <= mid; i++) 
      q[adj[indx][i].ss] = 1;
    if (ask(q) != cost)
      r = mid;
    else 
      l = mid+1;
  } 
  vector<int> q(m, 0);
  q[adj[indx][l].ss] = 1;
  if (ask(q) == cost)
    return indx;
  return find(adj[indx][l].ff, indx);
}

void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  n = n, m = U.size();
  adj.resize(N);
  for (int i = 0; i < m; i++) {
    adj[U[i]].pb({V[i], i});
    adj[V[i]].pb({U[i], i});
  }
  vector<int> q(m, 0);
  cost = ask(q);
  answer(0, find(0));
}

Compilation message (stderr)

highway.cpp: In function 'int find(int, int)':
highway.cpp:19:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   for (int i = 0; i < adj[indx].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~~

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