제출 #1278870

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278870		escobrand	경주 (Race) (IOI11_race)	C++20	100 / 100	345 ms	34208 KiB

race

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

using namespace std;
#define all(v) v.begin(),v.end()
#define pb push_back
#define ll long long
#define ld long double
#define fi first
#define se second
#define mk make_pair
typedef pair<int,int> pii;

const int maxn =2e5 + 10,maxv = 1e6 + 10,inf = 1e8 ;
int k;

int s[maxn],dp[maxv];

stack<int> st;
bool c[maxn];
int ans = inf;
vector<pii> adj[maxn];

void prep(int i,int p)
{
  s[i] = 1;
  for(auto [k,w] : adj[i])
  {
    if(k==p||c[k])continue;
    prep(k,i);
    s[i] += s[k];
  }
}

int fi(int i,int p,int sz)
{
  for(auto [k,w] : adj[i])
  {
    if(k==p||c[k])continue;
    if(s[k] * 2 >= sz)return fi(k,i,sz);
  }
  return i;
}

void cal(int i,int p,int tmp,int cnt)
{
  if(tmp>k)return;
  ans = min(ans,cnt + dp[k - tmp]);
  
  for(auto [k,w] : adj[i])
  {
    if(k==p||c[k])continue;
    cal(k,i,tmp+w,cnt+1);
  }
}

void fill(int i,int p,int tmp,int cnt)
{
  if(tmp > k)return;
  dp[tmp] = min(dp[tmp],cnt);
  st.push(tmp);
  for(auto [k,w] : adj[i])
  {
    if(k==p||c[k])continue;
    fill(k,i,tmp+w,cnt+1);
  }
}

void decompose(int i)
{
  prep(i,0);
  int cen = fi(i,0,s[i]);
  c[cen] = 1;
  // cout<<cen<<'\n';
  // 
  for(auto [k,w] : adj[cen])
  {
    if(!c[k])
    {
      cal(k,0,w,1);
      fill(k,0,w,1);
      // cout<<k<<'\n';
    }
  }
  for(;st.size();st.pop())if(st.top())dp[st.top()] = inf;
  
  for(auto [k,w] : adj[cen])
  {
    if(!c[k])decompose(k);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  k = K;
  for(int i = 1;i<maxv;i++)
  {
    dp[i] = inf;
  }
  
  for(int i = 0;i<N-1;i++)
  {
    H[i][0] ++;
    H[i][1] ++;
    adj[H[i][0]].pb(mk(H[i][1],L[i]));
    adj[H[i][1]].pb(mk(H[i][0],L[i]));
    // cout<<H[i][0]<<' '<<H[i][1]<<' '<<L[i]<<'\n';
  }
  
  decompose(1);
  if(ans==inf)ans=-1;
  return ans;
}

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