Submission #793524

#	Time	Username	Problem	Language	Result	Execution time	Memory
793524		limabeans	Race (IOI11_race)	C++17	0 / 100	3 ms	4948 KiB

race

#include <algorithm>
#include <iostream>
#include <vector>
#include <cassert>
#include <map>

using namespace std;
using ll = long long;
const int maxn=2e5+10;


vector<pair<ll,int>> g[maxn];

bool alive[maxn];
int siz[maxn];

int dfs(int at, int p) {
  siz[at] = 1;
  for (auto ed: g[at]) {
    int to = ed.second;
    if (to==p) continue;
    if (!alive[to]) continue;
    siz[at] += dfs(to, at);
  }
  return siz[at];
}

void dfs2(int at, int p, int &centroid, int cnt) {
  int hi = 0;
  for (auto ed: g[at]) {
    int to = ed.second;
    if (to==p) continue;
    if (!alive[to]) continue;
    dfs2(to,at,centroid,cnt);
    hi = max(hi, siz[to]);
  }
  hi = max(hi, cnt-siz[at]);
  //cout<<at<<": hi: "<<hi<<endl;
  if (hi+hi<=cnt) centroid=at;
}

int ans;
// dp[sum] = min_length
map<ll,int> solve(int at, ll k, int n) {
  dfs(at,at);
  int cnt = siz[at];
  int centroid = -1;
  dfs2(at,at,centroid,cnt);
  assert(~centroid);

  //cout<<at<<":--> "<<centroid<<endl;
  at = centroid;
  alive[at] = false;

  map<ll,int> dp;
  for (auto ed: g[at]) {
    int to = ed.second;
    if (alive[to]) {
      auto rec = solve(to, k, n);
      for (auto p: rec) {
	ll wei = ed.first + p.first;
	int len = p.second;
	if (dp.count(k-wei)) {
	  ans = min(ans, len+1+dp[k-wei]);
	}
      }
      for (auto p: rec) {
	ll wei = ed.first + p.first;
	int len = p.second;
	if (!dp.count(wei)) dp[wei]=n;
	dp[wei] = min(dp[wei], len+1);
      }
    }
  }

  dp[0] = 0;

  // cout<<"at: "<<at<<endl;
  // for (auto p: dp) cout<<p.first<<": "<<p.second<<endl;

  return dp;
}

int best_path(int n, int k, int H[][2], int L[]) {
  for (int i=0; i<n-1; i++) {
    int u=H[i][0];
    int v=H[i][1];
    int w=L[i];
    g[v].push_back({w,u});
    g[u].push_back({w,v});
  }
  
  for (int i=0; i<n; i++) {
    alive[i]=true;
  }
  ans = n;
  solve(0,k,n);
  if (ans == n) ans = -1;
  return ans;
}

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