Submission #421612

#	Time	Username	Problem	Language	Result	Execution time	Memory
421612		Sundavar	Highway Tolls (IOI18_highway)	C++14	51 / 100	3062 ms	22520 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
struct node{
  vector<pii> to;
  int depth = 0, cnt = 0;
  bool was = false;
};
vector<node> graph;
void DFS(int curr){
  graph[curr].was = true;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was)
      graph[a.first].depth = graph[curr].depth +1, DFS(a.first);
  graph[curr].was = false;
}
int middle = -1;
int cnt(int curr){
  graph[curr].was = true;
  graph[curr].cnt = 1;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was) graph[curr].cnt += cnt(a.first);
  graph[curr].was = false;
  return graph[curr].cnt;
}
int centroid(int curr, int si){
  graph[curr].was = true;
  int mxm = si - graph[curr].cnt, ans = -1;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was){
      mxm = max(mxm, graph[a.first].cnt);
      ans = max(ans, centroid(a.first, si));
    }
  if(mxm <= si/2) ans = curr;
  graph[curr].was = false;
  return ans;
}
void walk(int curr, vector<pii>& v){
  graph[curr].was = true;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was){
      v.push_back(a);
      walk(a.first, v);
    }
  graph[curr].was = false;
}
vector<int> lef,rig;
int getMiddle(vector<int> v, ll at, ll A, ll B){
  if(v.size() <= 2)
    return v[0];
  int cent = centroid(v[0], cnt(v[0]));
  int si = cnt(cent);
  int have = 0;
  vector<pii> v1, v2;
  graph[cent].was = true;
  for(pii& a : graph[cent].to){
    if(graph[a.first].was) continue;
    if(have + graph[a.first].cnt <= si/2)
      have += graph[a.first].cnt, v1.push_back(a), walk(a.first, v1);
    else
      v2.push_back(a), walk(a.first, v2);
  }
  graph[cent].was = false;
  vector<int> S(graph.size()-1, 0);
  for(pii& a : v1) S[a.second] = 1;
  ll d = ask(S);

  lef = {cent}, rig = {cent};
  for(pii& a : v1) lef.push_back(a.first);
  for(pii& a : v2) rig.push_back(a.first);
  if(d == at*A){
    for(pii& a : v1) graph[a.first].was = true;
    return getMiddle(rig, at, A, B);
  }
  else if(d == at*B){
    for(pii& a : v2) graph[a.first].was = true;
    return getMiddle(lef, at, A, B);
  }
  return cent;
}

void walk(int curr, vector<int>& s){
  graph[curr].was = true;
  for(pii& a : graph[curr].to)
    if(!graph[a.first].was)
      s[a.second] = 1, walk(a.first, s);
  graph[curr].was = false;
}

int get(int root, int N, ll at, ll A, ll B, vector<int> v){
  for(node& a : graph) a.was = true, a.depth = -1;
  graph[root].depth = 0;
  for(int& a : v) graph[a].was = false;
  DFS(root);
  vector<int> s(N-1, 0);
  walk(root, s);
  ll d = ask(s), depth = (d-at*A)/(B-A);
  if(depth == 0) return root;

  vector<pii> poss;
  for(int i = 0; i < N; i++)
    if(graph[i].depth == depth-1)
      for(pii& a : graph[i].to) 
        if(graph[a.first].depth == depth) poss.push_back(a);
  while(poss.size() > 1){
    s.assign(N-1, 0);
    for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
    if(ask(s) == (at-1)*A + B) poss.resize(poss.size()/2);
    else{
      vector<pii> uj;
      for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      poss = uj;
    }
  }
  return poss[0].first;
}
void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
  graph.resize(N);
  int M = U.size();
  for(int i = 0; i < M; i++){
    graph[U[i]].to.push_back({V[i],i});
    graph[V[i]].to.push_back({U[i],i});
  }
  vector<int> v(N);
  for(int i = 0; i < N; i++) v[i] = i;
  vector<int> s(M, 0);
  ll at = ask(s)/A;
  int middle = getMiddle(v, at, A, B);
  int S = get(middle, N, at, A, B, lef);
  int T = get(middle, N, at, A, B, rig);
  answer(S, T);

}

Compilation message (stderr)

highway.cpp: In function 'int get(int, int, ll, ll, ll, std::vector<int>)':
highway.cpp:109:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i = 0; i < poss.size()/2; i++) s[poss[i].second] = 1;
      |                    ~~^~~~~~~~~~~~~~~
highway.cpp:113:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |       for(int i = poss.size()/2; i < poss.size(); i++) uj.push_back(poss[i]);
      |                                  ~~^~~~~~~~~~~~~

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