Submission #709604

#	Time	Username	Problem	Language	Result	Execution time	Memory
709604		Ozy	Race (IOI11_race)	C++17	0 / 100	3059 ms	4948 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
#define des first
#define d second

vector<pll> hijos[MAX+2];
lli n,k,res,act,padre,mitad;
//centroid
lli tam[MAX+2],vis[MAX+2];
queue<lli> cola;
bool cond;
map<lli,lli> abso,rama;

void dfs(lli pos, lli p) {
    tam[pos] = 1;
    for(auto h : hijos[pos]) {
        if (vis[h.des] == 1 || h.des == p) continue;
        dfs(h.des,pos);
        tam[pos] += tam[h.des];
    }
}

void sub(lli pos, lli p,lli cam, lli sum) {

    //checa contra abso
    if (sum > k) return;
    lli a = k-sum;

    if (abso.find(a) != abso.end()) {
        a = abso[a] + cam;
        if (res == -1 || res > a) res = a;
    }

    //me meto a rama
    if (rama.find(sum) != rama.end()) rama[sum] = min(rama[sum],cam);
    else rama[sum] = cam;

    //sigo procesando el subarbol
    for(auto h : hijos[pos]) {
        if (h.des == padre || vis[h.des] == 1) continue;
        sub(h.des,pos,cam+1,sum+h.d);
    }
}

void solve(lli raiz) {

    abso.clear();
    abso[0] = 0;

    for(auto h : hijos[raiz]) {
        if (vis[h.des] == 1) continue;
        rama.clear();
        sub(h.des,raiz,1,h.d);

        if (rama.size() > abso.size()) swap(abso,rama);
        for (auto act : rama) {
            if (abso.find(act.first) != abso.end()) abso[act.first] = min(abso[act.first], act.second);
            else abso[act.first] = act.second;
        }
    }

}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
    k = K;
    res = -1;
    rep(i,0,n-2) {
        hijos[H[i][0]+1].push_back({H[i][1]+1, L[i]});
        hijos[H[i][1]+1].push_back({H[i][0]+1, L[i]});
    }

    cola.push(1);
    while(!cola.empty()){
        act = cola.front();
        cola.pop();

        dfs(act,0);                     //obtengo el centroide
        mitad = tam[act]/2;
        padre = 0;
        do{
            cond = false;
            for(auto h : hijos[act]) {
                if (h.des == padre || vis[h.des] == 1 || tam[h.des] <= mitad) continue;
                padre = act;
                act = h.des;
                cond = true;
                break;
            }
        }while(cond);

        solve(act);

        vis[act] = 1;
        for(auto h : hijos[act]) {
            if (vis[h.des] == 1) continue;
            cola.push(h.des);
        }
    }

    return res;
}

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