제출 #1288039

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1288039		bbbiros	Race (IOI11_race)	C++20	100 / 100	556 ms	129608 KiB

race

#include "race.h"
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <unordered_set>
#include <set>
#include <unordered_map>
#include <map>
#define ll long long
#define X first
#define Y second
using namespace std;
int n, k;
const int MAXN = 200010;
vector<pair<int,int>> v[MAXN];
int par[MAXN];
map<int, int> m[MAXN];
int ans=MAXN;
int depth[MAXN],depthlen[MAXN];
void dfs1(int beg,int par)
{
  for(auto nb:v[beg])
  {
    if(nb.X==par)continue;
    depth[nb.X]=depth[beg]+1;
    depthlen[nb.X]=depthlen[beg]+nb.Y;
    dfs1(nb.X,beg);
  }
}
int findpar(int x)
{
  if(par[x]==x)return x;
  return par[x]=findpar(par[x]);
}
void join(int a,int b,int lca)
{
  a=findpar(a);
  b=findpar(b);
  if(a==b)return;
  if(m[b].size()>m[a].size())m[a].swap(m[b]);
  for(auto [key,value] : m[b])
  {

    if(value==0)continue;
    int third=k-key+2*depthlen[lca];
    int anss=m[a][third];
    if(anss==0)continue;
    ans=min(ans,anss+value-2*depth[lca]);
  }
  for(auto [key,value] : m[b])
  {
    if(value==0)continue;
    if(m[a][key]==0 || m[a][key]>value)m[a][key]=value;
  }
  par[b]=a;
}
void dfs2(int beg,int par)
{
  for(auto nb:v[beg])
  {
    if(nb.X==par)continue;
    dfs2(nb.X,beg);
    join(beg,nb.X,beg);
  }
}
int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for (int i = 0; i < n-1; i++)
  {
    v[H[i][0]+1].push_back({H[i][1]+1,L[i]});
    v[H[i][1]+1].push_back({H[i][0]+1,L[i]});
  }
  depth[1]=0;
  depthlen[1]=0;
  dfs1(1,1);
  for(int i=1;i<=n;i++)
  {
    //cout<<i<<' '<<depth[i]<<" "<<depthlen[i]<<endl;
    par[i]=i;
    m[i][depthlen[i]]=depth[i];
  }
  dfs2(1,1);
  if(ans==MAXN)ans=-1;
  return ans;
}

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