Submission #1177542

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177542		LmaoLmao	Race (IOI11_race)	C++17	0 / 100	2 ms	4928 KiB

race

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;

const int INF = 1e9;

int s[200005];
bool del[200005];
vector<ii> adj[200005];
int mp[1000005];
int d,k,ans;

int dfs(int u,int p) {
    s[u]=1;
    for(ii v:adj[u]) {
        if(del[v.fi] || v.fi==p) continue;
        s[u]+=dfs(v.fi,u);
    }
    return s[u];
}
int citron(int u,int p,int sz) {
    for(ii v:adj[u]) {
        if(del[v.fi] || v.fi==p) continue;
        if(s[v.fi]*2>sz) return citron(v.fi,u,sz);
    }
    return u;
}
void get(int u,int p,int cur,int len,int type) {
    d=max(d,cur);
    if(len>k) return;
    if(type) {
        ans=min(ans,cur+mp[k-len]);
    }
    else {
        mp[len]=min(mp[len],cur);
    }
    //if(u==1 && cur==1) cout << mp[1];
    for(ii v:adj[u]) {
        if(v.fi!=p && !del[v.fi]) get(v.fi,u,cur+1,len+v.se,type);
    }
}
void build(int u) {
    int ctr=citron(u,0,dfs(u,0));
    d=0;
    del[ctr]=1;
    for(ii v:adj[ctr]) {
        if(!del[v.fi]) {
            get(v.fi,0,1,v.se,1);
            get(v.fi,0,1,v.se,0);
            //if(ctr==2) cout << k << ' ' << v << endl;
        }
    }
    //cout << ans << ' ' << d << endl;
    for(int i=1;i<=d;i++) {
        mp[i]=1e9;
    }
    for(ii v:adj[ctr]) {
        if(del[v.fi]) continue;
        build(v.fi);
    }
}

int best_path(int N, int K, int H[][2], int L[]){
  int n = N;
  k = K;
  for(int i = 0; i + 1 < n; ++i){
    int u = H[i][0]+1, v = H[i][1]+1, w = L[i];
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
  }
  for(int i=1;i<=k;i++) {
        mp[i]=1e9;
    }
    mp[0]=0;
    ans=1e9;
    build(1);
  return (ans == 1e9 ? -1 : ans);
}

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