Submission #586523

#	Time	Username	Problem	Language	Result	Execution time	Memory
586523		wdjpng	Highway Tolls (IOI18_highway)	C++17	0 / 100	262 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, c=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;
  pre[v]=c++;
  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;
  }
  post[v]=c++;
  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);
}

bool ischild(int w, int v)
{
  return pre[w]>=pre[v]&&post[w]<=post[v];
}

int lca(int a, int b)
{
  if(a==b) return a;

  if(dep[a]<dep[b]) swap(a,b);
  for(int j = 17; j >=0; j--) if(!ischild(b,up[a][j])) a=up[a][j];
  return up[a][0];
}

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

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


  int v2=leaves[end];
  int deplca=dep[lca(v1,v2)];
  int lca1 = lca(v2,v1);

  if(v1!=v2)
  {
     for(int j = 17; j >= 0; j--) 
    {
      if(dep[up[v1][j]]<deplca) continue;
      vector<signed>w(m,0);
      act(v, up[v1][j],0,1e8,w);
      act(v, v2,0,1e8,w);
      if(ask(w)==k*B) v1=up[v1][j];
    }

    for(int j = 17; j >= 0; j--) 
    {
      if(dep[up[v2][j]]<deplca) continue;
      vector<signed>w(m,0);
      act(v, up[v2][j],0,1e8,w);
      act(v, v1,0,1e8,w);
      if(ask(w)==k*B) v2=up[v2][j];
    }
  }
  else 
  {
    for(int j = 17; j >= 0; j--) 
    {
      vector<signed>w(m,0);
      act(v, up[v1][j],0,1e8,w);
      if(ask(w)<k*B) v1=up[v1][j];
    }
    {
      vector<signed>w(m,0);
      act(v,v1,0,1e8,w);
      if(ask(w)<k*B) v1=up[v1][0];
    }

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

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++)
......
   70 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                                   ~~~~~~~~~~
highway.cpp:70:31: note: in expansion of macro 'rep'
   70 |   for(int j = 1; j < 18; j++) rep(i,E.size()) up[i][j]=up[up[i][j-1]][j-1];
      |                               ^~~
highway.cpp:77: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]
   77 |     for(int i = cur; i < leaves.size(); i++)
      |                      ~~^~~~~~~~~~~~~~~
highway.cpp:104:7: warning: unused variable 'lca1' [-Wunused-variable]
  104 |   int lca1 = lca(v2,v1);
      |       ^~~~

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