Submission #229878

#	Time	Username	Problem	Language	Result	Execution time	Memory
229878		DavidDamian	Race (IOI11_race)	C++11	100 / 100	495 ms	89848 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
///Sack
///Determine the minimum length of a path that has sum k
struct edge
{
    int to;
    ll w;
};
vector<edge> adjList[200005];
int Size[200005];
int getSize(int u,int p)
{
    Size[u]=1;
    for(edge e: adjList[u]){
        int v=e.to;
        if(v==p) continue;
        Size[u]+=getSize(v,u);
    }
    return Size[u];
}
ll k;
ll minimum=INT_MAX;
map<ll,int>* sack[200005]; //<distance from the root, depth>
typedef pair<ll,int> pii;
void dfs(int u,int p,ll distRoot,int depth)
{
    int greatest=0,bigChild=-1;
    for(edge e: adjList[u]){
        int v=e.to;
        if(v==p) continue;
        dfs(v,u,distRoot+e.w,depth+1);
        if(Size[v]>greatest){
            greatest=Size[v];
            bigChild=v;
        }
    }
    if(bigChild==-1)
        sack[u]=new map<ll,int>;
    else
        sack[u]=sack[bigChild];
    for(edge e: adjList[u]){
        int v=e.to;
        if(v==p) continue;
        if(v==bigChild) continue;
        for(pii x: *sack[v]){ //Combine two lines in that subtree
            ll dist=x.first-distRoot;
            ll complement=k-dist+distRoot;
            if(complement>=0 && (*sack[u]).find(complement)!=(*sack[u]).end()){
                ll length=(*sack[u])[complement]+x.second;
                length-=(ll)2*depth;
                minimum=min(minimum,length);
            }
        }
        for(pii x: *sack[v]){ //Copy information from child
            if((*sack[u])[x.first]==0) (*sack[u])[x.first]=x.second;
            else{
                int length=(*sack[u])[x.first];
                (*sack[u])[x.first]=min(length,x.second);
            }
        }
    }
    if((*sack[u]).find(k+distRoot)!=(*sack[u]).end()){ //Check if a line has sum k
        ll length=(*sack[u])[k+distRoot];
        length-=depth;
        minimum=min(minimum,length);
    }
    if((*sack[u])[distRoot]==0) (*sack[u])[distRoot]=depth; //Add line from root to u to the sack
    else{
        int length=(*sack[u])[distRoot];
        (*sack[u])[distRoot]=min(length,depth);
    }
}
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]+1;
        int b=H[i][1]+1;
        ll w=L[i];
        adjList[a].push_back({b,w});
        adjList[b].push_back({a,w});
    }
    getSize(1,0);
    dfs(1,0,0,0);
    return (minimum!=INT_MAX)? minimum : -1;
}

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