제출 #1278873

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278873		escobrand	경주 (Race) (IOI11_race)	C++20	컴파일 에러	0 ms	0 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;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    
    
    int n,_;
    cin>>n>>_;
    int a[n][2];
    int b[n];
    
    for(int i = 0;i<n-1;i++)
    {
      cin>>a[i][0]>>a[i][1];
    }
    
    for(int i = 0;i<n-1;i++)
    {
      cin>>b[i];
    }
    
    cout<<best_path(n,_,a,b);
    
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccwxDotp.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccP4EEhJ.o:race.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status