Submission #714062

#	Time	Username	Problem	Language	Result	Execution time	Memory
714062		speedyArda	Race (IOI11_race)	C++14	0 / 100	3 ms	4948 KiB

race

#include "race.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
const int MAXN = 2e5+5;
vector< vector< pair<ll, int> > > adj(MAXN);
ll ans = 1e9;
int sz[MAXN];
int par_cent[MAXN];

pair<ll, ll> len[MAXN];
bool visited[MAXN];
int k;
//int cent;
void dfs_len(int v, int p, pair<ll, ll> prev)
{
  for(pair<ll, int> e : adj[v])
  {
    if(e.second == p || visited[e.second])
      continue;
    len[e.second].first = prev.first + e.first;
    len[e.second].second = prev.second + 1;
    dfs_len(e.second, v, len[e.second]);
  }
}
int dfs_sz(int v, int p)
{
  sz[v] = 1;
  for(pair<ll, int> e : adj[v])
  {
    if(e.second == p || visited[e.second])
      continue;
    int tmp = dfs_sz(e.second, v);
    sz[v] += tmp;

  }

  return sz[v];
}

int dfs_cent(int v, int p, int n)
{
    //cout << v << "\n";
    for(pair<ll, int> e : adj[v])
    {
        if(e.second == p || visited[e.second])
          continue;
        if(sz[e.second] * 2 > n)
          return dfs_cent(e.second, v, n);
    }

    return v;
}
pair<multiset<pair<ll, int> >, int > centroid(int v, int p)
{
    int n = dfs_sz(v, p);
    int cent = dfs_cent(v, p, n);

    visited[cent] = true;
    par_cent[cent] = p;
    multiset< pair<ll, int> > curr;
    curr.insert({0, 0});
    vector< pair<multiset<pair<ll, int> >, int> > allvals;
    dfs_len(cent, p, {0, 0});
    for(pair<ll, int> e : adj[cent])
    {
      if(e.second != p && !visited[e.second]) {
        pair<multiset<pair<ll, int> >, int> temp = centroid(e.second, cent);
        allvals.push_back(temp);
      }
    }

    for(pair<multiset<pair<ll, int> >, int> tmp : allvals)
    {
      for(pair<ll, int> l : tmp.first)
      {
        ll needed = k - l.first - len[tmp.second].first;
        auto it = curr.lower_bound({needed, 0});
        if(it == curr.end() || (*it).first != needed)
          continue;
        ans = min(ans, (*it).second + l.second + len[tmp.second].second);
        //if(ans == (*it).second + l.second + len[tmp.second].second)
          //cout << ans << " " << v << " " << tmp.second << " " << len[tmp.second].second << "\n";
      }


      for(pair<ll, int> l : tmp.first)
        curr.insert({l.first + len[tmp.second].first, l.second + len[tmp.second].second});
    }
    return {curr, cent};
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  for(int i = 0; i < N - 1; i++)
  {
    adj[H[i][0]].push_back({L[i], H[i][1]});
    adj[H[i][1]].push_back({L[i], H[i][0]});
  }

  centroid(0, -1);

  if(ans == 1e9)
    ans = -1;
  return ans;
}

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