Submission #1203842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203842		edga1	Race (IOI11_race)	C++20	100 / 100	478 ms	33220 KiB

race

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> a[200005];
int s[200005];
int d[200005], len[200005];
int best[1000005];
int rez=1e9,k,n;
vector<int> vert, vals;

int dfs(int x, int p){
    d[x]=1;
    for(int i=0; i<a[x].size(); i++){
        if(!s[a[x][i].first] && a[x][i].first!=p){
            d[x]+=dfs(a[x][i].first,x);
        }
    }
    return d[x];
}

int findc(int x){
    int sk=dfs(x,x);
    int e=1,v=x,p=x;
    while(e){
        e=0;
        if(sk-d[x]>sk/2) e=1;
        int m=0,mpos;
        for(int i=0; i<a[v].size(); i++){
            if(!s[a[v][i].first] && a[v][i].first!=p){
                if(d[a[v][i].first]>m){
                    m=d[a[v][i].first];
                    mpos=a[v][i].first;
                }
            }
        }
        if(m>sk/2) e=1;
        if(e==1){
            p=v;
            v=mpos;
        }
    }
    return v;
}

void dfs2(int x, int p){
    vert.push_back(x);
    for(auto [v,w] : a[x]){
        if(!s[v] && p!=v){
            len[v]=len[x]+1;
            d[v]=d[x]+w;
            if(d[v]>k) continue;
            dfs2(v,x);
        }
    }
}

void cd(int x){
    int c=findc(x);
    s[c]=1;
    best[0]=0;
    for(auto [v,w] : a[c]){
        if(s[v]==1) continue;
        vert.clear();
        len[v]=1;
        d[v]=w;
        dfs2(v,v);
        for(auto vi : vert){
            if(d[vi]<=k){
                rez=min(rez,len[vi]+best[k-d[vi]]);
            }
        }
        for(auto vi : vert){
            if(d[vi]<=k){
                best[d[vi]]=min(best[d[vi]],len[vi]);
                vals.push_back(d[vi]);
            }
        }
    }
    for(auto vi : vals){
        best[vi]=1e9;
    }
    vals.clear();
    for(auto [v,w] : a[c]){
        if(!s[v]) cd(v);
    }
}

int best_path(int N, int K, int h[][2], int l[]){
    k=K;
    n=N;
    for(int i=0; i<N-1; i++){
        a[h[i][0]].push_back({h[i][1],l[i]});
        a[h[i][1]].push_back({h[i][0],l[i]});
    }
    for(int i=1; i<1000005; i++) best[i]=1e9;
    cd(0);
    if(rez==1e9) return -1;
    return rez;
}

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