Submission #332573

# Submission time Handle Problem Language Result Execution time Memory
332573 2020-12-02T22:00:49 Z MilosMilutinovic Race (IOI11_race) C++14
0 / 100
223 ms 262144 KB
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=200050;
const int inf=1e9;
int ans=inf,sz[N],K,mn[5*N];
vector<pair<int,int>> E[N];
bool was[N];
int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];}
int Find(int u,int p,int n){for(auto e:E[u])if(e.first!=p&&!was[e.first]&&sz[e.first]*2>n)return Find(e.first,u,n);return u;}
int FindCentroid(int u){DFS(u,u);return Find(u,u,sz[u]);}
vector<pair<int,int>> all,tmp;
void Solve(int u,int p,int dep,int len){
    if(dep>K)return;
    //printf("%i %i %i %i\n",u,p,dep,len);
    all.pb({dep,len});
    tmp.pb({dep,len});
    if(K>=dep&&mn[K-dep]!=inf)ans=min(ans,len+mn[K-dep]);
    for(auto e:E[u])if(!was[e.first]&&e.first!=p)Solve(e.first,u,dep+e.second,len+1);
}
void Decompose(int u){
    u=FindCentroid(u);
    was[u]=1;mn[0]=0;
    tmp.pb({0,0});
    for(auto e:E[u]){
        if(!was[e.first]){
            Solve(e.first,u,e.second,1);
            for(auto c:all){
                if(mn[c.first]==inf)mn[c.first]=c.second;
                else mn[c.first]=min(mn[c.first],c.second);
            }
            all.clear();
        }
    }
    for(auto c:tmp)mn[c.first]=inf;
    tmp.clear();
    for(auto e:E[u])if(!was[e.first])Decompose(e.first);
}
int best_path(int n,int k,int h[][2],int l[]){
    K=k;
    for(int i=0;i<n-1;i++){
        E[h[i][0]].pb({h[i][1],l[i]});
        E[h[i][1]].pb({h[i][0],l[i]});
    }
    for(int i=0;i<5*N;i++)mn[i]=inf;
    Decompose(0);
    if(ans==inf)return -1;
    else return ans;
}

Compilation message

race.cpp: In function 'int DFS(int, int)':
race.cpp:10:109: warning: no return statement in function returning non-void [-Wreturn-type]
   10 | int DFS(int u,int p){sz[u]=1;for(auto e:E[u])if(e.first!=p&&!was[e.first])DFS(e.first,u),sz[u]+=sz[e.first];}
      |                                                                                                             ^
# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 223 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -