Submission #479628

#	Time	Username	Problem	Language	Result	Execution time	Memory
479628		kamalsharmaa9	Race (IOI11_race)	C++14	9 / 100	174 ms	42800 KiB

race

#include<bits/stdc++.h>
#include <cstdio>
using namespace std;

#define N              200005
#define ff              first
#define ss              second
#define ll         long long
#define pb              push_back
#define pii             pair<ll,ll>
#define mod             1000000007
#define inf             1e18
vector<ll>gr[N];
map<ll, ll>edge[N];
map<ll, ll>m[N];
ll depth[N];
ll fin_ans;
ll val[N];
ll k;

ll dfs(ll node, ll par)
{
  ll sz = -1;
  ll ind;
  ll not_child = 1;
  for (auto child : gr[node])
  {
    if (child != par )
    {
      not_child = 0;
      ll temp = dfs(child, node);
      if (temp > sz)
      {
        sz = temp;
        ind = child;
      }
    }
  }
  if (not_child == 1) {
    val[node] = 0;
    depth[node] = 0;
    return 0;
  }
  for (auto child : gr[node])
  {
    if (child == par)
      continue;
    ll to_find = k - edge[node][child];
    if (to_find == 0)
      fin_ans = 1;
    to_find = to_find - val[child];
    if (m[child].find(to_find) != m[child].end())
    {
      fin_ans = min(fin_ans, 1 + depth[child] - m[child][to_find]);
    }
  }
  m[node].swap(m[ind]);
  depth[node] = depth[ind] + 1;
  val[node] = val[ind] + edge[node][ind];
  m[node][edge[node][ind] - val[node]] = depth[node] - 1;
  m[ind].clear();
  ////////////////////////////////alll deal with child to node
  // and inserted bigger_child and done with that
  for (auto child : gr[node])
  {
    if (child != par && child != ind)
    {
      for (auto i : m[child])
      {
        ll num = i.ff + val[child] + edge[node][child];
        ll to_find = k - num - val[node];
        if (m[node].find(to_find) != m[node].end())
        {
          fin_ans = min(fin_ans, depth[node] - m[node][to_find] + depth[child] - i.ss + 1);
        }
      }
      ll findd = k - edge[node][child] - val[node];
      if (m[node].find(findd) != m[node].end())
      {
        fin_ans = min(fin_ans, depth[node] - m[node][findd] + 1);
      }
      for (auto i : m[child])
      {
        ll num = i.ff + val[child];

        ll to_insert = num - val[node];

        ll newd = depth[node] - 1 - (depth[child] - i.ss);
        if (m[node].find(to_insert) != m[node].end())
        {
          if (m[node][to_insert] < newd)
            m[node][to_insert] = newd;
        }
        else
          m[node][to_insert] = newd;

      }
      m[node][edge[node][child] - val[node]] = depth[node] - 1;
      m[child].clear();
    }
  }
  return m[node].size();
}

int  best_path(int  n, int  K, int  H[][2], int  L[]) {
  ll i, a, b, c;
  k = (ll)K;
  for (ll i = 0; i <= n; i++)
  {
    gr[i].clear();
    m[i].clear();
    depth[i] = 0;
    val[i] = 0;
    edge[i].clear();
  }
  fin_ans = inf;
  for (i = 0; i < n - 1; i++) {
    a = H[i][0]; b = H[i][1]; c = L[i];
    a++; b++;
    edge[a][b] = c;
    edge[b][a] = c;
    gr[a].pb(b);
    gr[b].pb(a);
  }

  dfs(1, 0);
  if (fin_ans == inf )
    return -1;
  return (int )fin_ans;
}

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