제출 #1127909

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127909		Sofiatpc	경주 (Race) (IOI11_race)	C++20	0 / 100	10 ms	14400 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 add[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 + add[f] + w;
      if(mp[p].find(k - d - add[p]) != mp[p].end()) ans = min(ans, mp[p][k-d-add[p]]+it.sc+1);
    }
    //Adiciona
    for(auto it : mp[f]){
      int id = it.fi + add[f] + w - add[p];
      if( mp[p].find(id) == mp[p].end())mp[p][id] = it.sc+1;
      else mp[p][id] = min(mp[p][id], it.sc+1);
    }
    mp[f].clear();
  }else{
    //Conta
    for(auto it : mp[p]){
      int d = it.fi + add[p] + w;
      if(mp[f].find(k - d - add[f]) != mp[f].end()) ans = min(ans, mp[f][k-d-add[f]]+it.sc+1);
    }
    //Adiciona
    add[f] += w;
    for(auto it : mp[p]){
      int id = it.fi + add[p] - add[f];
      if( mp[f].find(id) == mp[f].end())mp[f][id] = it.sc+1;
      else mp[f][id] = min(mp[f][id], it.sc+1);
    }
    mp[p].clear();
    swap(mp[p],mp[f]);
    swap(add[p],add[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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57