Submission #409560

#	Time	Username	Problem	Language	Result	Execution time	Memory
409560		600Mihnea	Race (IOI11_race)	C++17	100 / 100	1037 ms	61288 KiB

race

#include <bits/stdc++.h>
#include "race.h"

using namespace std;

typedef long long ll;
const int N = 200000 + 7;
int n, k, best, sz[N], total;
ll dist[N];
bool vis[N];
vector<pair<int, int>> g[N];

void build(int a, int p = -1) {
  sz[a] = 1;
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      build(b, a);
      sz[a] += sz[b];
    }
  }
}

int fcen(int a, int p = -1) {
  int mx = total - sz[a];
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      mx = max(mx, sz[b]);
    }
  }
  if (mx <= total / 2) {
    return a;
  }
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b] && mx == sz[b]) {
      return fcen(b, a);
    }
  }
  assert(0);
}

vector<pair<ll, int>> dists;

void dfs(int a, int p, int step) {
  dists.push_back({dist[a], step});
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (b != p && !vis[b]) {
      dist[b] = dist[a] + cost;
      dfs(b, a, step + 1);
    }
  }
}

void solve(int a) {
  build(a);
  total = sz[a];
  a = fcen(a);
  vis[a] = 1;
  map<ll, int> mn;
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (!vis[b]) {
      dists.clear();
      dist[b] = cost;
      dfs(b, a, 1);
      for (auto &val : dists) {
        int other = k - val.first;
        if (val.first == k) {
          best = min(best, val.second);
        }
        if (mn.count(other)) {
          best = min(best, mn[other] + val.second);
        }
      }
      for (auto &val : dists) {
        if (!mn.count(val.first)) {
          mn[val.first] = val.second;
        } else {
          mn[val.first] = min(mn[val.first], val.second);
        }
      }
    }
  }
  for (auto &edge : g[a]) {
    int b = edge.first, cost = edge.second;
    if (!vis[b]) {
      solve(b);
    }
  }
}

int best_path(int nodes, int target, int edges[][2], int len_edges[]) {
  best = N;
  n = nodes;
  k = target;
  for (int i = 0; i < n; i++) {
    vis[i] = 0;
    g[i].clear();
  }
  for (int i = 0; i < n - 1; i++) {
    g[edges[i][0]].push_back({edges[i][1], len_edges[i]});
    g[edges[i][1]].push_back({edges[i][0], len_edges[i]});
  }
  solve(0);
  if (best == N) {
    best = -1;
  }
  return best;
}

Compilation message (stderr)

race.cpp: In function 'void build(int, int)':
race.cpp:16:25: warning: unused variable 'cost' [-Wunused-variable]
   16 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp: In function 'int fcen(int, int)':
race.cpp:27:25: warning: unused variable 'cost' [-Wunused-variable]
   27 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp:36:25: warning: unused variable 'cost' [-Wunused-variable]
   36 |     int b = edge.first, cost = edge.second;
      |                         ^~~~
race.cpp: In function 'void solve(int)':
race.cpp:88:25: warning: unused variable 'cost' [-Wunused-variable]
   88 |     int b = edge.first, cost = edge.second;
      |                         ^~~~

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