Submission #593743

#	Time	Username	Problem	Language	Result	Execution time	Memory
593743		KrisjanisP	Race (IOI11_race)	C++17	9 / 100	165 ms	12724 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;

// find the centroid
// of a connected component
ll findCentroid(ll v)
{
  return v;
}

// 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;
  if(found[o]!=-1) return found[o]+d;
  for(auto& [u,w]: AL[v])
  {
    if(u==p) continue;
    if(removed[u]) continue;
    return check(u,v,d+1,s+w);
  }
  return -1;
}

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;
    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);
  }
  if(found[K]!=-1)
  {
      if(res!=-1) res = min(res,found[K]); 
      else res = found[K];
  }
  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 c = findCentroid(v);
  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: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57