Submission #1034784

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034784		aymanrs	Highway Tolls (IOI18_highway)	C++14	18 / 100	304 ms	262144 KiB

highway

#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
  int p;
  vector<pair<node*, int>> l;
  int d;
};
void dfs(node* n, node* p, int d){
  n->d = d;
  for(auto [c,x] : n->l){
    if(c==p) continue;
    c->p = x;
    dfs(c, n, d+1);
  }
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  node g[N];
  int m = U.size();
  bool tsub = true;
  for(int i = 0;i < U.size();i++){
    tsub &= U[i]==i && V[i]==i+1;
    g[U[i]].l.emplace_back(&g[V[i]], i);
    g[V[i]].l.emplace_back(&g[U[i]], i);
  }
  vector<int> w(m, 0);
  long long dis = ask(w)/A;
  if(tsub){
    int l = 0, r = N-1, mid;
    while(l<r){
      mid = l+r+1>>1;
      for(int i = l;i < mid;i++) w[i]=1;
      long long re = ask(w);
      for(int i = l;i < mid;i++) w[i]=0;
      if(re > dis*A) r=mid-1;
      else l = mid;
    }
    answer(l,l+dis);
    return;
  }
  dfs(&g[0], NULL, 0);
  vector<pair<int, int>> v;
  for(int i = 1;i < N;i++) if(g[i].d == dis) v.emplace_back(g[i].p, i);
  int l = 0, r = v.size()-1, mid;
  while(l<r){
    mid = l+r>>1;
    for(int i = l;i <= mid;i++) w[v[i].first] = 1;
    long long re = ask(w);
    for(int i = l;i <= mid;i++) w[v[i].first] = 0;
    if(re > dis*A){
      r = mid;
    } else l = mid+1;
  }
  answer(0, v[l].second);
}

Compilation message (stderr)

highway.cpp: In function 'void dfs(node*, node*, int)':
highway.cpp:11:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   11 |   for(auto [c,x] : n->l){
      |            ^
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(int i = 0;i < U.size();i++){
      |                 ~~^~~~~~~~~~
highway.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |       mid = l+r+1>>1;
      |             ~~~^~
highway.cpp:46:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |     mid = l+r>>1;
      |           ~^~

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