Submission #1262577

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262577		avohado	Race (IOI11_race)	C++20	9 / 100	116 ms	10856 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define maxn 200005
#define f first
#define s second
#define ll long long
#define pb(x) push_back(x)
int n, k, l[maxn], sh=INT_MAX, v=-1;
vector<pair<int, int>> g[maxn];
int z[maxn], k1[maxn];
bool used[maxn];
int dfs1(int u, int p, int n){
    int sh=1;
    for(auto i:g[u]){
        if(!used[i.f]&&i.f!=p){
            sh+=dfs1(i.f, u, n);
        }
    }
    if(v!=-1&&sh>=n/2){
        v=u;
    }
    z[u]=sh;
    return sh;
}
void dfs2(int u, int p, int ck, int cnt){
    if(k1[k-ck]!=-1){
        sh=min(sh, k1[k-ck]+cnt);
    }
    for(auto i:g[u]){
        if(i.f!=p&&!used[i.f]&&ck+l[i.s]<=k){
            dfs2(i.f, u, ck+l[i.s], cnt+1);
        }
    }
    k1[ck]=min(cnt, k1[ck]);
}
void rem(int n, int u){
    if(n==1){
        return;
    }
    v=-1;
    dfs1(u, u, n);
    for(int i=1; i<=k; i++){
        k1[i]=-1;
    }
    for(auto i:g[u]){
        if(!used[i.f]&&l[i.s]<=k){
            dfs2(i.f, u, l[i.s],1);
        }
    }
    used[u]=1;
    for(auto i:g[u]){
        if(!used[i.f]){
            rem(z[u], i.f);
        }
    }
}
int best_path(int n1, int k1, int h1[][2], int l1[]){
    n=n1, k=k1;
    for(int i=1; i<n; i++){
        g[h1[i-1][0]].push_back({h1[i-1][1], i-1});
        g[h1[i-1][1]].push_back({h1[i-1][0], i-1});
    }
    for(int i=0; i<n-1; i++){
        l[i]=l1[i];
    }
    rem(n, 0);
    return (sh==INT_MAX?-1:sh);
}

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