Submission #1123664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123664		_uros9	Race (IOI11_race)	C++20	100 / 100	367 ms	31484 KiB

race

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

const int MAXN=200009,INF=1000000009;

int dist[1000009];
int siz[MAXN];
bool was[MAXN];
int X;
vector<int> za_brisati;
vector<pair<int,int>> graf[MAXN];
int init_siz(int node,int pret){
    siz[node]=1;
    for(auto x:graf[node]){
        if(x.first==pret||was[x.first]) continue;
        siz[node]+=init_siz(x.first,node);
    }
    return siz[node];
}
int Centroid(int node,int pret,int n){
    for(auto x:graf[node]){
        if(x.first==pret||was[x.first]) continue;
        if(siz[x.first]*2>n) return Centroid(x.first,node,n);
    }
    return node;
}

int rez=INF;

void C_query(int node,int pret,int tr_dist,int brojac){
    if(tr_dist>X) return;
    za_brisati.push_back(tr_dist);
    rez=min(rez,brojac+dist[X-tr_dist]);
    for(auto x:graf[node]){
        if(x.first==pret||was[x.first]) continue;
        C_query(x.first,node,tr_dist+x.second,brojac+1);
    }
}
void C_upd(int node,int pret,int tr_dist,int brojac){
    if(tr_dist>X) return;
    dist[tr_dist]=min(dist[tr_dist],brojac);
    for(auto x:graf[node]){
        if(x.first==pret||was[x.first]) continue;
        C_upd(x.first,node,tr_dist+x.second,brojac+1);
    }
}




void CD(int poc){
    int n=init_siz(poc,-1);
    int C=Centroid(poc,-1,n);
    dist[0]=0;
    for(auto x:graf[C]){
        if(was[x.first]) continue;
        C_query(x.first,C,x.second,1);
        C_upd(x.first,C,x.second,1);
    }
    for(auto x:za_brisati) dist[x]=INF;
    za_brisati.clear();
    was[C]=1;
    for(auto x:graf[C]){
        if(was[x.first]) continue;
        CD(x.first);
    }

}



int best_path(int N, int K, int H[][2], int L[]){
    X=K;
    for(int i=0; i<1000009; i++) dist[i]=INF;
    for(int i=0; i<N-1; i++){
        int a=H[i][0],b=H[i][1],w=L[i];
        graf[a].push_back({b,w});
        graf[b].push_back({a,w});
    }
    CD(0);
    if(K==0) return 0;
    return (rez<MAXN?rez:-1);
}

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