Submission #82791

#	Time	Username	Problem	Language	Result	Execution time	Memory
82791		vibster	Race (IOI11_race)	C++14	100 / 100	1823 ms	158172 KiB

race

#include "race.h"
#include<bits/stdc++.h>
#define endl '\n'
#define INF 1e18

typedef long long int ll;

using namespace std;

const int NMAX=2e5+1, LOGN=19, NMAX2=1e6+1;
int sz[NMAX];
ll k;
vector <set<pair<int,int>>> node(NMAX);
multiset <int> dis[NMAX2];
ll ans=INF;

//Decompose
//subtree size
int dfs0(int u, int p){
    sz[u]=1;
    for(auto b: node[u]){
        if(b.first==p)continue;
        sz[u]+=dfs0(b.first, u);
    }
    return sz[u];
}
//find centroid
int dfs1(int u, int p, int n){
    for(auto b:node[u]){
        if(b.first==p)continue;
        if(sz[b.first]>n/2)return dfs1(b.first, u, n);
    }
    return u;
}
//updating dist multiset
void dfs2(int u, int p, ll dista, int len, bool s){
    if(dista<=k)
    if(s)dis[dista].insert(len);
    else if(dis[dista].find(len)!=dis[dista].end())dis[dista].erase(dis[dista].find(len));
    for(auto b:node[u]){
        if(b.first==p)continue;
        dfs2(b.first,u,dista+b.second, len+1,s);
    }
}
//upading ans
void dfs3(int u, int p, ll dista, int len){
    if((ll)k-dista>=0 && !dis[k-dista].empty())ans=min(ans,(ll) (*dis[k-dista].begin())+len);
    for(auto b:node[u]){
        if(b.first==p)continue;
        dfs3(b.first, u, dista+b.second, len+1);
    }
}
//Decompose
void Decompose(int u, int p){
    int n=dfs0(u,p);
    int centroid=dfs1(u,p,n);
    dfs2(centroid, p, 0, 0, 1);
    for(auto b:node[centroid]){
        if(b.first==p)continue;
        dfs2(b.first,centroid,b.second,1,0);
        dfs3(b.first,centroid,b.second,1);
    }
    for(auto b:node[centroid]){
        if(b.first==p)continue;
        node[b.first].erase({centroid,b.second});
        Decompose(b.first, centroid);
    }
    node[centroid].clear();
}
int best_path(int N, int K, int H[][2], int L[]){
    k=K;
  for(int i=0; i<N-1; i++){
    node[H[i][0]].insert({H[i][1],L[i]});
    node[H[i][1]].insert({H[i][0],L[i]});
    }
    Decompose(0,-1);
    if(ans>=INF)return -1;
    else return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs2(int, int, ll, int, bool)':
race.cpp:37:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
     if(dista<=k)
       ^

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