Submission #1271148

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271148		danilofv	Race (IOI11_race)	C++20	0 / 100	6 ms	324 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);

void calc_subtrees(ll src, vector<ll>& subtrees, vector<vector<pair<ll, ll>>>& grafo, ll parent){

    subtrees[src] = 1;
    for (auto vz: grafo[src]){
        if (parent == vz.first) continue;
        calc_subtrees(vz.first, subtrees, grafo, src);
      
        subtrees[src] += subtrees[vz.first];
    }
}


ll centroid(ll src, vector<ll>& subtrees, vector<vector<pair<ll,ll>>>& grafo, ll parent){
    for (auto vz: grafo[src]){
        if (parent == vz.first) continue;
        if (subtrees[vz.first] > grafo.size()/2){
            return centroid(vz.first, subtrees, grafo, src);
        }
    }

    return src;
}

ll find_centroid(vector<vector<pair<ll, ll>>> grafo, ll beg, ll parent){
    ll n = grafo.size();
    vector<ll> subtrees(n);
    calc_subtrees(beg, subtrees, grafo, parent);    

    return centroid(beg, subtrees, grafo, -1);

}

ll minCam = INT_MAX;
unordered_map<ll, ll> melhor; // melhor caminho que chega naquela raiz com tamanho sendo a chave e o número de arestas sendo o valor

void dfs1(ll src, ll parent, ll currPathTam, ll currPathArestas, ll K){

    if (melhor.find(K - currPathTam) != melhor.end())
        minCam = min(minCam, currPathArestas + melhor[K - currPathTam]);

    for (int i = 0; i< grafo[src].size() ; i++){
        auto [vz, w] =  grafo[src][i];

        if (parent == vz) continue;
        
        dfs1(vz, src, currPathTam + w, currPathArestas + 1, K);
        // Agora, percorreu todas as subárvores, volta atualizando
        dfs2(vz, src, currPathTam + w, currPathArestas + 1);
    }

    // Daqui pra baixo não precisa mais do melhor, faz o mesmo para o centroid de cada subárvore,    
}

void dfs2(ll src, ll parent, ll currPathTam, ll currPathArestas){
    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) continue;
        dfs2(vz, src, currPathTam + w, currPathArestas + 1);
    }
}

void dfs3(ll src, ll parent, ll K){
    auto cntd = find_centroid(grafo, src, parent);
    melhor.clear();
    dfs1(cntd, src, 0, 0, K);
    for (auto &[vz, w]: grafo[src]){
        if (vz == parent) continue;
        dfs3(vz, src, K);
    }
}


int best_path(int N, int K, int H[][2], int L[])
{
    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]});
    }

    dfs3(0, -1, K);

    return minCam;
}

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