Submission #1127919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127919		Sofiatpc	Race (IOI11_race)	C++20	100 / 100	378 ms	55856 KiB

race

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

using namespace std;

#define fi first
#define sc second
#define sz(v) (int)v.size()
const int MAX = 2*1e5+5;
vector< pair<int,int> > adj[MAX];
map< int,int > mp[MAX];
int da[MAX], dq[MAX], ans, k;

void merge(int p, int f, int w){
  if(sz(mp[p]) >= sz(mp[f])){
    //Conta
    for(auto it : mp[f]){
      int d = it.fi + da[f] + w;
      if(mp[p].find(k - d - da[p]) != mp[p].end()) ans = min(ans, mp[p][k-d-da[p]]+dq[p] +it.sc+dq[f] +1);
    }
    //Adiciona
    for(auto it : mp[f]){
      int id = it.fi + da[f] + w - da[p];
      if( mp[p].find(id) == mp[p].end())mp[p][id] = it.sc+dq[f] +1 -dq[p];
      else mp[p][id] = min(mp[p][id]+dq[p], it.sc+dq[f] +1) - dq[p];
    }
    mp[f].clear();
  }else{
    //Conta
    for(auto it : mp[p]){
      int d = it.fi + da[p] + w;
      if(mp[f].find(k - d - da[f]) != mp[f].end()) ans = min(ans, mp[f][k-d-da[f]]+dq[f] +it.sc+dq[p] +1);
    }
    //Adiciona
    da[f] += w; dq[f]++;
    for(auto it : mp[p]){
      int id = it.fi + da[p] - da[f];
      if( mp[f].find(id) == mp[f].end())mp[f][id] = it.sc+dq[p] - dq[f];
      else mp[f][id] = min(mp[f][id]+dq[f], it.sc+dq[p]) - dq[f];
    }

    mp[p].clear();
    swap(mp[p],mp[f]);
    swap(da[p],da[f]);
    swap(dq[p],dq[f]);
  }
}

void dfs(int s, int p){
  mp[s][0] = 0;
  for(int i = 0; i < sz(adj[s]); i++){
    int viz = adj[s][i].fi, w = adj[s][i].sc;
    if(viz != p){
      dfs(viz,s);
      merge(s,viz,w);
    }
  }

}

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

  ans = n+1; k = K;

  dfs(0,-1);

  if(ans == n+1)ans = -1;

  return ans;
}

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