Submission #953443

#	Time	Username	Problem	Language	Result	Execution time	Memory
953443		vjudge1	Race (IOI11_race)	C++98	0 / 100	7 ms	12892 KiB

race

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

struct ari{
    int v, w;
};

int n, k;
vector<vector<ari>> adj;
int subar[200001];
bool used[200001];
int ans=(1<<30);
int pesos[1000001];

void dfs(int node, int ant){
    subar[node]=1;
    for(auto h: adj[node]){
        if(h.v==ant || used[h.v])
            continue;
        dfs(h.v, node);
        subar[node]+=subar[h.v];
    }
}

int centroid(int node, int ant, int tam){
    for(auto h: adj[node]){
        if(h.v==ant || used[h.v])
            continue;
        if(subar[h.v]>tam/2)
            return centroid(h.v, node, tam);
    }
    return node;
}

void explora(int node, int cnt, int sum, int ant){
    if(sum>k)
        return;
    subar[node]=1;
    if(pesos[sum]==0)
        pesos[sum]=cnt;
    else
        pesos[sum]=min(pesos[sum], cnt);
    for(auto h: adj[node]){
        if(h.v==ant || used[h.v])
            continue;
        explora(h.v, cnt+1, sum+h.w, node);
        subar[node]+=subar[h.v];
    }
}

void checa(int node, int cnt, int sum, int ant){
    subar[node]=1;
    if(k-sum>0 && pesos[k-sum]!=0)
        ans=min(pesos[k-sum]+cnt, ans);
    for(auto h: adj[node]){
        if(used[h.v] || h.v==ant)
            continue;
        checa(h.v, cnt+1, sum+h.w, node);
        subar[node]+=subar[h.v];
    }
    if(pesos[sum]==0)
        pesos[sum]=cnt;
    else
        pesos[sum]=min(pesos[sum], cnt);
}

void limpia(int node, int sum, int ant){
    if(sum<1000000)
        pesos[sum]=0;
    if(sum>k)
        return;
    for(auto h: adj[node]){
        if(h.v==ant || used[node])
            continue;
        limpia(h.v, sum+h.w, node);
    }
}

void busca(int node, int tam){
    bool ya=0;
    used[node]=1;
    for(auto h: adj[node]){
        if(used[h.v])
            continue; 
        if(!ya){
            explora(h.v, 1, h.w, node);
            ya=1;
        }
        else{
            checa(h.v, 1, h.w, h.v);
        }
    }
    if(pesos[k]!=0)
        ans=min(ans, pesos[k]);
    for(auto h: adj[node]){
        if(used[h.v])
            continue;
        limpia(h.v, h.w, node);
    }
    for(auto h: adj[node]){
        if(used[h.v])
            continue;
        int cen=centroid(h.v, node, subar[h.v]);
        busca(cen, subar[h.v]);
    }
}

int best_path(int N, int K, int H[][2], int L[]){   
    n=N; k=K;
    adj.resize(n+1);
    for(int i=0; i<n-1; i++){
        adj[H[i][0]].push_back({H[i][1], L[i]});
        adj[H[i][1]].push_back({H[i][0], L[i]});
    }
    dfs(0, 0);
    int cen=centroid(0, 0, n);
    busca(cen, n);
    if(ans==(1<<30))
        return -1;
    return ans;
}

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