Submission #1149951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149951		knhatdev	Race (IOI11_race)	C++20	100 / 100	321 ms	52952 KiB

race

#include<bits/stdc++.h>
#define str string
#define task "strdel"
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N=1e6+5,lg=20,mod=2e9+7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u,int v){
 return u+rd()%(v-u+1);
}
int n,dp[N],k,ans=1e9;
vector<ii>a[N];
int sz[N];
bool check[N];
void dfs(int u,int cha){
  sz[u]=1;
  for(ii v:a[u]){
    if(check[v.fi]||v.fi==cha)continue;
    dfs(v.fi,u);
    sz[u]+=sz[v.fi];
  }
}
int fin(int u,int cha,int n){
  for(ii v:a[u]){
    if(!check[v.fi]&&v.fi!=cha&&sz[v.fi]>n/2)
      return fin(v.fi,u,n);
  }
  return u;
}
void add(int u,int cha,int sum,int canh){
  if(sum>k)return;
  // cout <<u<<" "<<sum<<" "<<canh<<" "<<cha <<'\n';
  ans=min(ans,canh+dp[k-sum]);
  for(ii v:a[u]){
    if(v.fi==cha||check[v.fi])continue;
    add(v.fi,u,v.se+sum,canh+1);
  }
}
stack<int>s;
// int maxx=0;
void them(int u,int cha,int sum,int canh){
  if(sum>k)return;
  dp[sum]=min(dp[sum],canh);
  s.push(sum);
  // maxx=max(maxx,sum);
  for(ii v:a[u]){
    if(v.fi==cha||check[v.fi])continue;
    them(v.fi,u,v.se+sum,canh+1);
  }
}
void buildcen(int u,int cha){
  dfs(u,-1);
  int g=fin(u,-1,sz[u]);
  check[g]=true;

  for(ii v:a[g]){
    if(v.fi==cha||check[v.fi])continue;
    add(v.fi,g,v.se,1);
    them(v.fi,g,v.se,1);
  }
  // cout<<'\n';
while(!s.empty()){
  if(s.top()!=0)dp[s.top()]=1e9;
  s.pop();
}
  for(ii v:a[g]){
    if(v.fi==cha||check[v.fi])continue;
    buildcen(v.fi,g);
  }
}
// int b[N][2];
// int w[N];
int  best_path(int N,int K,int H[][2],int w[]){
  // cin >> n >> k;
   n=N,k=K;

  // for(int i=1;i<n;++i)cin >> b[i][0]>>b[i][1];
    for(int i=0;i<n-1;++i){
      int u=H[i][0]+1,v=H[i][1]+1;
      // cin >> w;
      a[u].emb(v,w[i]);
      a[v].emb(u,w[i]);
    }
    for(int i=1;i<=k;++i)dp[i]=1e9;
  buildcen(1,-1);
 return (ans==1e9?-1:ans);


}

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