Submission #593819

#	Time	Username	Problem	Language	Result	Execution time	Memory
593819		KrisjanisP	Race (IOI11_race)	C++17	43 / 100	3059 ms	33980 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<ll,ll>;

const ll MXN = 2e5;
const ll MXK = 1e6;

vector<ii> AL[MXN];
bool removed[MXN];

ll N, K;

ll subtreeSize[MXN];

// get size of a subtree
ll getSize(ll v, ll p)
{
  ll res = 1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    res += getSize(u,v);
  }
  subtreeSize[v] = res;
  return res;
}

// find the centroid
// of a connected component
ll findCentroid(ll v, ll p, ll n)
{
  bool found = true;
  ll sum = 1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    sum += subtreeSize[u];
    if(subtreeSize[u]>(n/2))
    {
      found = false;
      break;
    }
  }
  if((n-sum)>(n/2)) found = false;
  if(found) return v;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    ll r = findCentroid(u,v,n);
    if(r!=-1) return r;
  }
  return -1;
}

// saves the depth at which was found
// the minimum depth and the second minimum
ll found[MXK+1];

void gather(ll v, ll p, ll d, ll s)
{
  if(s>K) return;
  if(found[s]==-1) found[s] = d;
  else found[s] = min(found[s],d);
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    gather(u,v,d+1,s+w);
  }
}

ll check(ll v, ll p, ll d, ll s)
{
  if(s>K) return -1;
  ll o = K-s;
  ll res = -1;
  if(found[o]!=-1) res = found[o]+d;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    ll r = check(u,v,d+1,s+w);
    if(r!=-1)
    {
      if(res!=-1) res = min(res,r); 
      else res = r;
    }
  }
  return res;
}

void clear(ll v, ll p, ll s)
{
  if(s>K) return;
  found[s] = -1;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    clear(u,v,s+w);
  }
}

// returns -1 or minimum highways
// such that v is included in the path
ll process(ll v)
{
  vector<ll> vec;

  ll res = -1;
  for(auto& [u,w]: AL[v])
  {
    if(removed[u]) continue;
    found[0]=0;
    ll r = check(u,v,1,w);
    if(r!=-1)
    {
      if(res!=-1) res = min(res,r); 
      else res = r;
    }
    gather(u,v,1,w);
  }

  for(auto& [u,w]: AL[v]) clear(u,v,w);

  return res;
}

// returns -1 or minimum highways
// in the whole connected component
// divide and conquer
ll DACE(ll v)
{
  ll sz = getSize(v,v);
  ll c = findCentroid(v,v,sz);
  ll res = process(c);
  removed[c] = 1;
  for(auto& [u,w]: AL[c])
  {
    if(removed[u]) continue;
    ll res_u = DACE(u);
    if(res_u!=-1){
      if(res==-1) res=res_u;
      else res=min(res, res_u);
    }
  }
  return res;
}

int best_path(int n, int k, int H[][2], int L[])
{
  N = n,K = k;
  for(ll i=1;i<=K;i++) found[i]=-1;
  for(ll i=0;i<N-1;i++)
  {
    ll a=H[i][0],b=H[i][1],w=L[i];
    AL[a].emplace_back(b,w);
    AL[b].emplace_back(a,w);
  }
  return DACE(0);
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 0 / 57