Submission #229673

#	Time	Username	Problem	Language	Result	Execution time	Memory
229673		DavidDamian	Race (IOI11_race)	C++11	21 / 100	162 ms	62072 KiB

race

//#include "race.h"
#include<bits/stdc++.h>
using namespace std;
///Subtask 3
///DFS with buckets
typedef long long ll;
struct edge
{
    int to;
    ll w;
};
vector<edge> adjList[200005];
int k;
int minimum=INT_MAX;
void dfs_sub2(int u,int p,int depth,ll path)
{
    if(path==k) minimum=min(minimum,depth);
    for(edge e: adjList[u]){
        int v=e.to;
        ll w=e.w;
        if(p==v) continue;
        dfs_sub2(v,u,depth+1,path+w);
    }
}
ll parent_way[200005];
void fillParent(int u,int p)
{
    for(edge e: adjList[u]){
        int v=e.to;
        ll w=e.w;
        if(v==p) continue;
        parent_way[v]=w;
        fillParent(v,u);
    }
}
vector<int>* bucket[200005];
void dfs(int u,int p)
{
    int leaf=1;
    for(edge e: adjList[u]){
        int v=e.to;
        ll w=e.w;
        if(p==v) continue;
        leaf=0;
        dfs(v,u);
    }
    bucket[u]=new vector<int>(101);
    for(edge e: adjList[u]){
        int v=e.to;
        ll w=e.w;
        if(p==v) continue;
        for(int i=0;i<k;i++){
            int path_child=(*bucket[v])[i];
            int path=(*bucket[u])[k-i];
            if(path_child==0) continue;
            if(path!=0)
                minimum=min(minimum,path_child+path);
            if((*bucket[u])[i]==0)
                (*bucket[u])[i]=path_child;
            else
                (*bucket[u])[i]=min((*bucket[u])[i],path_child);
        }
        if((*bucket[v])[k]!=0) minimum=min(minimum,(*bucket[v])[k]);
    }
    if(leaf) (*bucket[u])[ parent_way[u] ]=1;
    if((*bucket[u])[k]!=0)
        minimum=min(minimum,(*bucket[u])[k]);
    if(!leaf){
        for(int i=k;i>=1;i--){
            if((ll)i+parent_way[u]>k) continue;
            int dist=i+parent_way[u];
            if((*bucket[u])[i]!=0){
                (*bucket[u])[dist]=(*bucket[u])[i]+1;
                if(dist!=i) (*bucket[u])[i]=0;
            }
        }
        (*bucket[u])[ parent_way[u] ]=1;
    }
}
int best_path(int n, int K, int H[][2], int L[])
{
    k=K;
    for(int i=0;i<n-1;i++){
        int a=H[i][0];
        int b=H[i][1];
        ll w=L[i];
        adjList[a].push_back({b,w});
        adjList[b].push_back({a,w});
    }
    if(n<=1000){
        for(int u=0;u<n;u++){
            dfs_sub2(u,-1,0,0);
        }
        return (minimum!=INT_MAX)? minimum : -1;
    }
    fillParent(0,-1);
    dfs(0,-1);
    /*for(int i=0;i<n;i++){
        cout<<i<<":";
        for(int j=0;j<=k;j++){
            if((*bucket[i])[j]!=0) cout<<j<<" "<<(*bucket[i])[j]<<endl;
        }
        cout<<endl;
    }*/
    return (minimum!=INT_MAX)? minimum : -1;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:42:12: warning: unused variable 'w' [-Wunused-variable]
         ll w=e.w;
            ^
race.cpp:50:12: warning: unused variable 'w' [-Wunused-variable]
         ll w=e.w;
            ^

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