Submission #151421

#	Time	Username	Problem	Language	Result	Execution time	Memory
151421		flashmt	Race (IOI11_race)	C++17	Compilation error	0 ms	0 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 main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int x, y, z;
  cin >> n >> k;
  for (int i = 1; i < n; i++)
  {
    cin >> x >> y >> z;
    a[x].push_back({y, z});
    a[y].push_back({x, z});
  }
  par[0] = -1;
  dfs(0);
  cout << (ans != oo ? ans : -1) << endl;
}

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;
   ~~~~~~~~~~~^~~~~~
/tmp/cck9ZjZ2.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/cc3gI2hV.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/cc3gI2hV.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status