Submission #1126662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126662		ntdaccode	Race (IOI11_race)	C++17	100 / 100	344 ms	34512 KiB

race

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define ii pair<int,long long>
#define fi first
#define se second
#define pb push_back
using namespace std;
const int mod=1e9+7;
const int M=1e6+10;
const int N=2e5+10;
int n,k;
vector<ii> ke[N];
bool dd[N];
int sz[N];
int child(int u,int p=0)
{
  sz[u]=1;
  for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]) sz[u]+=child(v,u);
  return sz[u];
}
int centroid(int u,int p=0)
{
  for(auto [v,w]:ke[u]) if(v!=p&&!dd[v]&&sz[v]>n/2) return centroid(v,u);
  return u;
}
int mi[M],kq=1e9;
vector<int> wdel;
void dfs(int u,int tt,int val,int depth,int p=0)
{
  if(val>k) return ;
  if(!tt) {
    kq=min(kq,depth+mi[k-val]);
  }
  else {
    if(mi[val]==1e9) wdel.pb(val);
    mi[val]=min(mi[val],depth);
  }
  for(auto [v,w] :ke[u]) if(v!=p&&!dd[v]) dfs(v,tt,val+w,depth+1,u);
}
void solve(int u)
{
  n=child(u);
  int root=centroid(u);
  dd[root]=true;
  for(auto [v,w] : ke[root]) {
    if(!dd[v]) {
      dfs(v,0,w,1);
      dfs(v,1,w,1);
    }
  }
  for(int v: wdel) mi[v]=1e9;
  wdel.clear();
  for(auto [v,w] :ke[root]){
    if(!dd[v]) solve(v);
  }
}

int best_path(int N, int K, int H[][2], int L[])
{
  n = N;
  k = K;
  for(int i = 0;i <= n - 2; i++) {
    H[i][0]++;
    H[i][1]++;
    ke[H[i][0]].pb({H[i][1],L[i]});
    ke[H[i][1]].pb({H[i][0],L[i]});
  }
  fori(i,1,1e6) mi[i]=1e9;
  mi[0]=0;
  solve(1);
  return (kq==1e9 ? -1 : kq) ;
}

//int32_t main()
//{
//  ios_base::sync_with_stdio(0);
//  cin.tie(0);
//  cout.tie(0);
//  #define task "1"
//  if(fopen(task".inp","r"))
//  {
//    freopen(task".inp","r",stdin);
//    freopen(task".out","w",stdout);
//  }
//  cin >> n >> k;
//  fori(i,1,n-1)
//  {
//    int u,v,w;
//    cin >> u >> v >> w;
//    u++;
//    v++;
//    ke[u].pb({v,w});
//    ke[v].pb({u,w});
//  }
//  fori(i,1,1e6) mi[i]=1e9;
//  mi[0]=0;
//  solve(1);
//  cout << (kq==1e9 ? -1 : kq) ;
//}

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