Submission #151422

#	Time	Username	Problem	Language	Result	Execution time	Memory
151422		flashmt	Race (IOI11_race)	C++17	100 / 100	569 ms	50540 KiB

race

#include <bits/stdc++.h>
using namespace std;
const int N = 200200, oo = 1 << 21;

int n, k, h[N][2], l[N], height[N], pos[N], deltaVal[N], st[N], last, curChild[N], par[N];
long long deltaID[N];
vector<pair<int, int>> a[N];
vector<int> order;
map<long long, int> m[N];
int ans = oo;

int unionMap(int u, int v, int c)
{
  int res = oo;
  long long offsetID = c + deltaID[u] + deltaID[v];
  int offsetVal = 1 + deltaVal[u] + deltaVal[v];

  for (auto it : m[v])
  	if (m[u].count(k - it.first - offsetID))
      res = min(res, it.second + m[u][k - it.first - offsetID] + offsetVal);

  offsetID = c + deltaID[v] - deltaID[u];
  offsetVal = 1 + deltaVal[v] - deltaVal[u];

  for (auto it : m[v])
  	if (!m[u].count(it.first + offsetID) || m[u][it.first + offsetID] > it.second + offsetVal)
      m[u][it.first + offsetID] = it.second + offsetVal;

  m[v].clear();
  return res;
}

int calc(int x)
{
  int mxSize = 0, res = oo, tmp;
  pos[x] = x;

  for (auto u : a[x])
  {
  	int y = u.first;
  	if (y == par[x]) continue;
  	int sizeY = m[pos[y]].size();
  	if (sizeY > mxSize)
    {
      mxSize = sizeY;
      pos[x] = pos[y];
      tmp = u.second;
    }
  }

  if (pos[x] == x)
  {
  	m[x][0] = 0;
  	return res;
  }

  int u = pos[x];
  deltaID[u] += tmp;
  deltaVal[u]++;
  if (m[u].count(k - deltaID[u]))
  	res = min(res, m[u][k - deltaID[u]] + deltaVal[u]);
  if (!m[u].count(-deltaID[u]) || m[u][-deltaID[u]] > -deltaVal[u])
  	m[u][-deltaID[u]] = -deltaVal[u];

  for (auto u : a[x])
  {
  	int y = u.first;
  	if (y == par[x] || pos[x] == pos[y]) continue;
  	res = min(res, unionMap(pos[x], pos[y], u.second));
  }

  return res;
}

void dfs(int x)
{
  for (auto u : a[x])
  {
    int y = u.first;
    if (y == par[x])
      continue;
    par[y] = x;
    dfs(y);
  }
  ans = min(ans, calc(x));
}

int best_path(int _n, int _k, int h[][2], int l[])
{
  n = _n;
  k = _k;
  for (int i = 0; i < n - 1; i++)
  {
    a[h[i][0]].push_back({h[i][1], l[i]});
    a[h[i][1]].push_back({h[i][0], l[i]});
  }
  par[0] = -1;
  dfs(0);
  return ans == oo ? -1 : ans;
}

Compilation message (stderr)

race.cpp: In function 'int calc(int)':
race.cpp:58:14: warning: 'tmp' may be used uninitialized in this function [-Wmaybe-uninitialized]
   deltaID[u] += tmp;
   ~~~~~~~~~~~^~~~~~

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