Submission #1245673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245673		julia_08	Race (IOI11_race)	C++20	0 / 100	7 ms	14408 KiB

race

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

using namespace std;

using ll = long long;

const int MAXN = 2e5 + 10;

ll dist[MAXN];

vector<pair<int, ll>> adj[MAXN];

map<ll, int> freq[MAXN];

int ans, k;

void merge(int u, int v, int d){

  if(freq[u].size() > freq[v].size()) swap(freq[u], freq[v]);

  for(auto x : freq[u]){
    if(freq[v].count(k + 2 * dist[v] - x.first)){
      ans = min(ans, x.second + freq[v][k + 2 * dist[v] - x.first] - 2 * d);
    }
  }

  for(auto x : freq[u]) freq[v][x.first] += x.second;

  freq[u].clear();

}

void dfs(int v, int p, int d){

  freq[v][dist[v]] = d;

  for(auto [u, w] : adj[v]){
    if(u != p){
      dist[u] = dist[v] + w;
      dfs(u, v, d + 1);
      merge(u, v, d);
    }
  }

}

int best_path(int n, int k_, int h[][2], int l[]){

  for(int i=1; i<=n; i++){
    adj[i].clear();
    freq[i].clear();
  }
    
  k = k_;

  for(int i=0; i<n-1; i++){
    adj[h[i][0] + 1].push_back({h[i][1] + 1, l[i]});
    adj[h[i][1] + 1].push_back({h[i][0] + 1, l[i]});
  }

  ans = 1e9;

  dfs(1, 1, 0);

  return (ans == 1e9 ? -1 : ans);

}

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