Submission #148661

#	Time	Username	Problem	Language	Result	Execution time	Memory
148661		anonymous	Race (IOI11_race)	C++14	21 / 100	605 ms	20564 KiB

race

#include "race.h"
#include<vector>
#include<map>
#include<utility>
#include<iostream>
using namespace std;
vector <pair<int,int> > adj[200005];
map <int,pair<pair<int,int>, pair<int,int> > > M;
bool del[200005];
int Size[200005],SubtreeSize, Centroid, out=42069666,K;

int genSize(int u, int prev) {
    if (del[u]) {return(0);}
    Size[u]=1; //size
    for (auto v: adj[u]) {
        if (v.first != prev) {Size[u]+=genSize(v.first,u);}
    }
    return(Size[u]);
}

void genDists(int u, int depth, int e, int prev, int branch) { //generate distances from root
    //printf("derp");
    if (depth>(1<<20) or del[u]) {return;}
    if (M.find(depth) == M.end()) {
        M[depth].first.first=branch; //{branch, e}
        M[depth].first.second=e;
        M[depth].second.first=-1;
        M[depth].second.second=1<<30;
    } else {
        if (M[depth].first.second>=e) {
            M[depth].second.second=M[depth].first.second;
            M[depth].second.first=M[depth].first.first;
            M[depth].first.second=e;
            M[depth].first.first=branch;
        } else if (M[depth].second.second>=e) {
            M[depth].second.second=e;
            M[depth].second.first=branch;
        }
    }
    //printf("%d %d\n",depth,M[depth]);
    for (auto v: adj[u]) {
        if (v.first != prev) {genDists(v.first,depth+v.second,e+1,u, e ? branch: v.first);} //e is number of edges used
    }
}

void FindCentroid(int u, int prev) {
    if (del[u] or Centroid or SubtreeSize<=1) {return;}
    bool good=true; //break if node done, centroid found, subtree bad
    for (auto v: adj[u]) {
        if ((!del[v.first]) and v.first != prev and 2*Size[v.first]>SubtreeSize) {
            //printf("%d %d %d\n",u,v.first,Size[v.first]);
            good=false;
            break;
        }
    }
    if (Size[u]*2<SubtreeSize) {good=false;}
    if (good) {
        genDists(u,0,0,0,0);
        for (auto val: M) {
            if (M.find(K-val.first) != M.end()) {
                if (M[K-val.first].first.first != val.second.first.first) {
                    out=min(out,val.second.first.second+M[K-val.first].first.second);
                    //printf("%d %d\n",val.first,val.second.first.second+M[K-val.first].first.second);
                }
                if (M[K-val.first].second.first != val.second.first.first) {
                    out=min(out,val.second.first.second+M[K-val.first].second.second);
                    //printf("%d %d\n",val.first,val.second.first.second+M[K-val.first].first.second);
                }
            }
        }
        Centroid=u;
        del[u]=true;
    } else {
        for (auto v: adj[u]) {
            if (v.first != prev) {FindCentroid(v.first,u);}
        }
    }
}

void calcAnswer(int u) {
    if (del[u]) {return;}
    SubtreeSize=genSize(u,0);
    FindCentroid(u,0);
    //printf("CENTROID IS %d. Subtree Size is %d\n",Centroid,SubtreeSize);
    int temp=Centroid;
    Centroid=0;
    M.clear();
    for (auto v: adj[temp]) {
        calcAnswer(v.first);
    }
}

int best_path(int n, int k, int H[][2], int L[]) {
    K=k;
    for (int i=0; i<n-1; i++) {
        adj[H[i][0]+1].push_back({H[i][1]+1,L[i]});
        adj[H[i][1]+1].push_back({H[i][0]+1,L[i]});
    } //1 indexify
    calcAnswer(1);
    return(out<=n ? out : -1);
}

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