Submission #586499

#	Time	Username	Problem	Language	Result	Execution time	Memory
586499		wdjpng	Highway Tolls (IOI18_highway)	C++17	12 / 100	244 ms	262144 KiB

highway

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

#define int long long
#define all(a) a.begin(), a.end()
#define rep(i,n) for(int i = 0; i<n; i++)

using namespace std;

int k,m;

struct edge
{
  int w, i;
};

int N=90000, c1=0, c2=0;
vector<vector<edge>>E;
vector<int>p(N);
vector<int>ped(N,-1);
vector<int>pre(N,-1);
vector<int>post(N,-1);
vector<int>dep(N,0);
vector<vector<int>>up(N,vector<int>(18,0));

vector<int> dfs(int v, int par)
{
  if(par==-1) up[v][0]=v;
  p[v]=par;
  vector<int>cr;
  if(E[v].size()==1) cr.push_back(v);
  for(auto [w,i] : E[v]) if(w!=par) 
  {
    dep[w]=dep[v]+1;
    vector<int> ans = dfs(w,v);
    ped[w]=i;
    if(ans.size()>cr.size()) swap(cr,ans);
    for(int x : ans) cr.push_back(x);
    up[w][0]=v;
  }
  return cr;
}

void act(int to, int v, int c, int lim, vector<signed>&w)
{
  if(v==to||ped[v]==-1||w[ped[v]]||c==lim) return;
  w[ped[v]]=true;
  act(to,p[v],c+1, lim, w);
}


void findr(int v, int A, int B)
{
  vector<int>leaves=dfs(v,-1);
  for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];

  int start = 0, end = leaves.size();
  while (end-start>1)
  {
    vector<signed>w(m,0);
    int cur = (start+end)/2;
    for(int i = cur; i < leaves.size(); i++)
    {
      act(v,leaves[i],0,1e8,w);
    }

    if(k*B==ask(w)) start=cur;
    else end=cur;
  }

  int cle=leaves[start];
  for(int j = 17; j >= 0; j--) 
  {
    vector<signed>w(m,0);
    act(v, up[cle][j],0,1e8,w);
    if(ask(w)==k*B) cle=up[cle][j];
  }

  answer(0,cle);
}

void find_pair(signed n, std::vector<signed> U, std::vector<signed> V, signed A, signed B) {
  E.assign(n, vector<edge>());
  m = U.size();
  rep(i,m)
  {
    E[U[i]].push_back({V[i],i});
    E[V[i]].push_back({U[i],i});
  }
  vector<signed>tmp(m,0);
  k=ask(tmp)/A;

  findr(0,A,B);
}

Compilation message (stderr)

highway.cpp: In function 'void findr(long long int, long long int, long long int)':
highway.cpp:6:34: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<edge> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i,n) for(int i = 0; i<n; i++)
......
   55 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                                   ~~~~~~~~~~
highway.cpp:55:31: note: in expansion of macro 'rep'
   55 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                               ^~~
highway.cpp:62:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = cur; i < leaves.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~

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