Submission #106566

#	Time	Username	Problem	Language	Result	Execution time	Memory
106566		tictaccat	Highway Tolls (IOI18_highway)	C++14	12 / 100	206 ms	7812 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int N,A,B,M,depthT;
vector<vector<pair<int,int>>> adj;
vector<pair<int,int>> pos;

void dfs(int u, int depth, int p) {
//  cout << u << " " << pos.size() << "\n";
  for (auto e: adj[u]) {
    int v,k; tie(v,k) = e;
    if (v == p) continue;
    if (depth+1 == depthT) pos.push_back(e);
    else dfs(v,depth+1,u);
  }
}

void find_pair(int tempN, std::vector<int> U, std::vector<int> V, int tempA, int tempB) {

  N = tempN; A = tempA; B = tempB; M = U.size(); adj.resize(N); 

  for (int i = 0; i < M; i++) {
    adj[U[i]].push_back(make_pair(V[i],i));
    adj[V[i]].push_back(make_pair(U[i],i));
  }

  vector<int> w(M,0);
  depthT = ask(w)/A;

  dfs(0,0,-1);

  while (pos.size() > 1) {
    int mid = pos.size()/2;
    for (int i = 0; i < mid; i++) w[pos[i].second] = 0;
    for (int i = mid; i < pos.size(); i++) w[pos[i].second] = 1;
    if (ask(w) == (ll)depthT*A) {
      pos.erase(pos.begin()+mid,pos.end());
    }
    else {
      pos.erase(pos.begin(),pos.begin()+mid);
    }
  }

  //cout << pos[0].first << "\n";

  answer(0, pos[0].first);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:39:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = mid; i < pos.size(); i++) w[pos[i].second] = 1;
                       ~~^~~~~~~~~~~~

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