Submission #904804

#	Time	Username	Problem	Language	Result	Execution time	Memory
904804		ALTAKEXE	Race (IOI11_race)	C++14	100 / 100	346 ms	76652 KiB

race

#include "race.h"
#include "bits/stdc++.h"
#define MAXN 200009
#define INF 1000000007
#define mp(x, y) make_pair(x, y)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
#define ppb() pop_back()
#define tr(ii, c) for (__typeof((c).begin()) ii = (c).begin(); ii != (c).end(); ii++)
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
template <class T>
bool umin(T &a, T b)
{
  if (a > b)
  {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
bool umax(T &a, T b)
{
  if (a < b)
  {
    a = b;
    return 1;
  }
  return 0;
}
int n, k, ans = INF;
ll dis[MAXN];
vector<PII> adj[MAXN];
set<pair<ll, int>> s[MAXN];
void dfs(int nd, int pr, int lvl)
{
  tr(it, adj[nd])
  {
    int to = it->ff;
    if (to != pr)
    {
      dis[to] = dis[nd] + it->ss;
      dfs(to, nd, lvl + 1);
      if ((int)s[to].size() > (int)s[nd].size())
        swap(s[to], s[nd]);
      __typeof((s[nd]).begin()) itt;
      tr(it, s[to]) if (dis[nd] * 2 + k >= it->ff)
      {
        itt = s[nd].lower_bound(mp(dis[nd] * 2 + k - it->ff, -1));
        if (itt != s[nd].end() and itt->ff + it->ff == k + dis[nd] * 2)
          umin(ans, it->ss + itt->ss - 2 * lvl);
      }
      tr(it, s[to]) s[nd].insert(*it);
      s[to].clear();
    }
  }
  s[nd].insert(mp(dis[nd], lvl));
  __typeof((s[nd]).begin()) itt = s[nd].lower_bound(mp(k + dis[nd], -1));
  if (itt != s[nd].end() and itt->ff - dis[nd] == k)
    umin(ans, itt->ss - lvl);
}
int best_path(int N, int K, int h[][2], int l[])
{
  n = N, k = K;
  for (int i = 0; i < n - 1; i++)
  {
    int u = h[i][0], v = h[i][1];
    adj[u].pb(mp(v, l[i]));
    adj[v].pb(mp(u, l[i]));
  }
  dfs(1, -1, 0);
  if (ans == INF)
    ans = -1;
  return ans;
}

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