Submission #873072

#	Time	Username	Problem	Language	Result	Execution time	Memory
873072		andre_stan	Race (IOI11_race)	C++14	0 / 100	3 ms	18780 KiB

race

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = (int)2e5 + 5;
const int M = (int)1e6 + 5;
const int inf = (int)1e9;

int h[N + 1][2], l[N + 1];

set<pair<int, int> > G[N];
int n, k, sz[N], exist[M], edgecnt[M], tt;

int dfs(int u, int p) {
  sz[u] = 1;
  for(auto it : G[u]) if(it.first != p) {
    sz[u] += dfs(it.first, u);
  }
  return sz[u];
}
int centroid(int u, int p, int nn) {
  for(auto it : G[u]) if(it.first != p) {
    if(sz[it.first] > nn / 2) return centroid(it.first, u, nn);
  }
  return u;
}
int dfs2(int u, int p, int d, int cnt, int t, vector<pair<int, int> >& v) {
  int want = k - d, ans = inf;
  if(want >= 0 && exist[want] == t) {
    ans = min(ans, cnt + edgecnt[want]);
  }
  if(d <= k) {
    v.push_back({d, cnt});
    for(auto it : G[u]) if(it.first != p) {
      ans = min(ans, dfs2(it.first, u, d + it.second, cnt + 1, t, v));
    }
  }
  return ans;
}
int Solve(int u, int p) {
  int nn = dfs(u, p);
  int c = centroid(u, p, nn);
  int ans = inf;

  int t = ++tt;
  exist[0] = t; edgecnt[0] = 0;
  for(auto it : G[c]) { // dfs one subtree at a time
    vector<pair<int, int> > tmp;
    ans = min(ans, dfs2(it.first, c, it.second, 1, t, tmp));
    for(auto itt : tmp) {
      if(exist[itt.first] != t || (exist[itt.first] == t && edgecnt[itt.first] > itt.second)) {
        exist[itt.first] = t;
        edgecnt[itt.first] = itt.second;
      }
    }
  }
  vector<pair<int, int> > tmp(G[c].begin(), G[c].end());
  for(auto it : tmp) {
    G[c].erase(it); G[it.first].erase({c, it.second});
    ans = min(ans, Solve(it.first, c));
  }

  return ans;
}

int best_path (int n, int k, int h[][2], int l[])
{
    for (int i = 0; i < n - 1; ++i)
    {
        G[h[i][0]].insert({h[i][1], l[i]});
        G[h[i][1]].insert ({h[i][0], l[i]});
    }

    tt = 0;
  int ans = Solve(0, -1);
  if (ans == inf)ans = -1;
  return ans;
  cout << (ans == inf ? -1 : ans) << '\n';
}

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