Submission #142595

#	Time	Username	Problem	Language	Result	Execution time	Memory
142595		anonymous	Race (IOI11_race)	C++14	0 / 100	6 ms	5240 KiB

race

#include "race.h"
#include<vector>
#include<map>
#include<utility>
#include<iostream>
using namespace std;
vector <pair<int,int> > adj[200005];
map <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) { //generate distances from root
    if (depth>(1<<20) or del[u]) {return;}
    if (M.find(depth) == M.end()) {
        M[depth]=e;
    } else {
        M[depth]=min(M[depth],e);
    }
    for (auto v: adj[u]) {
        if (v.first != prev) {genDists(v.first,depth+v.second,e+1,u);} //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 (2*Size[v.first]>SubtreeSize) {
            good=false;
            break;
        }
    }
    if (good) {
        genDists(u,0,0,0);
        for (auto val: M) {
            if (M.find(K-val.first) != M.end()) {
                out=min(out,val.second+M[K-val.first]);
            }
        }
        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);
    int temp=Centroid;
    Centroid=0;
    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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57