Submission #1271464

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271464		danilofv	Race (IOI11_race)	C++20	21 / 100	3097 ms	43552 KiB

race

#include <bits/stdc++.h>
using namespace std;
#define ll long long

vector<vector<pair<ll, ll>>> grafo;
void dfs2(ll src, ll parent, ll currPathTam, ll currPathArestas);
vector<ll> subtrees;
vector<bool> visited;
ll minCam = INT_MAX;
unordered_map<ll, ll> melhor;
void calc_subtrees(ll src, ll parent){
    subtrees[src] = 1;
    for (auto& vz: grafo[src]){
        ll v = vz.first;
        if (v == parent || visited[v]) continue; 
        calc_subtrees(v, src);
        subtrees[src] += subtrees[v];
    }
}

ll centroid(ll src, ll parent, ll subTreeSize){
    for (auto vz: grafo[src]){
        ll v = vz.first;
        if (v == parent || visited[v]) continue; 
        if (subtrees[v] > subTreeSize/2){
            return centroid(v, src, subTreeSize);
        }
    }
    return src;
}

ll find_centroid(ll beg, ll parent){
    // subtrees.assign(grafo.size(), 0);        
    calc_subtrees(beg, parent);
    return centroid(beg, -1, subtrees[beg]);
}

void dfs1(ll src, ll parent, ll currPathTam, ll currPathArestas, ll K){
    if (visited[src]) return; 
    if (melhor.find(K - currPathTam) != melhor.end())
        minCam = min(minCam, currPathArestas + melhor[K - currPathTam]);

    for (int i = 0; i< (int)grafo[src].size() ; i++){
        auto [vz, w] =  grafo[src][i];
        if (parent == vz || visited[vz]) continue; 
        dfs1(vz, src, currPathTam + w, currPathArestas + 1, K);
    }
}

void dfs2(ll src, ll parent, ll currPathTam, ll currPathArestas){
    if (visited[src]) return;
    if (melhor.find(currPathTam)!= melhor.end())
        melhor[currPathTam ] = min(melhor[currPathTam], currPathArestas);
    else
        melhor[currPathTam] = currPathArestas;

    for (auto &[vz, w]: grafo[src]){
        if (vz == parent || visited[vz]) continue;
        dfs2(vz, src, currPathTam + w, currPathArestas + 1);
    }
}

void solve(ll start, ll K){
    ll cntd = find_centroid(start, -1);

    visited[cntd] = true;

    melhor.clear();
    melhor[0] = 0;
    for (auto [v, w] : grafo[cntd]){
        if (visited[v]) continue;
        dfs1(v, cntd, w, 1, K);
        dfs2(v, cntd, w, 1);
    }

    for (auto [v, w] : grafo[cntd]){
        if (!visited[v]){
            solve(v, K);
        }
    }
}


int best_path(int N, int K, int H[][2], int L[])
{
    minCam = INT_MAX;
    visited.assign(N, false);
    subtrees.assign(N, 0);
    grafo.resize(N);
    for (int i = 0; i < N - 1; i++)
    {
        grafo[H[i][0]].push_back({H[i][1], L[i]});
        grafo[H[i][1]].push_back({H[i][0], L[i]});
    }

    solve(0,K);

    return (minCam == INT_MAX ? -1 : minCam);
}

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