Submission #1034801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034801		aymanrs	Highway Tolls (IOI18_highway)	C++17	51 / 100	201 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, id;
};
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 zfs(node* n, node* p, vector<node*>& o){
  for(auto [c,x] : n->l){
    if(c!=p) zfs(c, n, o);
  }
  o.push_back(n);
}
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);
  }
  for(int i = 0;i < N;i++) g[i].id = i;
  vector<int> w(m, 0);vector<node*> o;
  zfs(&g[0], NULL, o);
  long long dis = ask(w)/A;
  int l = 0, r = N-1, mid;
  while(l<r){
    mid=l+r>>1;
    for(int i = l;i <= mid;i++){
      for(auto [c,x] : o[i]->l) w[x]=1;
    }
    long long re = ask(w);
    for(int i = l;i <= mid;i++){
      for(auto [c,x] : o[i]->l) w[x]=0;
    }
    if(re>dis*A){
      r = mid;
    } else {
      l=mid+1;
    }
  }
  int s = o[l]->id;
  dfs(o[l], NULL, 0);
  vector<pair<int, int>> v;
  for(int i = 0;i < N;i++) if(g[i].d == dis) v.emplace_back(g[i].p, i);
  l = 0; r = v.size()-1;
  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(s, v[l].second);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   for(int i = 0;i < U.size();i++){
      |                 ~~^~~~~~~~~~
highway.cpp:38:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     mid=l+r>>1;
      |         ~^~
highway.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |     mid = l+r>>1;
      |           ~^~

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