Submission #1270827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270827		ian_otoni	Race (IOI11_race)	C++20	0 / 100	0 ms	328 KiB

race

#include<bits/stdc++.h>
#include "race.h"

using namespace std;

#define INF 999999999

int calcula_tam_subarvores(int nodo, int pai, vector<set<int>> &adj, vector<int> &sub){
    sub[nodo] = 1;

    for(int filho : adj[nodo]){
        if(filho!=pai) sub[nodo] += calcula_tam_subarvores(filho, nodo, adj, sub);
    }

    return sub[nodo];
}

int acha_centroide(int nodo, int pai, int n, vector<set<int>> &adj, vector<int> &sub){
    for(int filho : adj[nodo]){
        if(filho!=pai && sub[filho]>n/2) return acha_centroide(filho, nodo, n, adj, sub);
    }

    return nodo;
}

unordered_map<int, unordered_map<int,int>> costs;
int ans = INF;

void dfs1(int start_node, int parent_node, vector<set<int>> &adj, unordered_map<int, int> &melhor, unordered_map<int, int> &memoria, int k){

	stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso
	st.push(make_tuple(start_node, parent_node, 1, costs[parent_node][start_node])); //coloca determinado filho do centroide na pilha
	
	while(!st.empty()){
        int node, pai, distancia_da_raiz, peso_ate_araiz;
        tie(node, pai, distancia_da_raiz, peso_ate_araiz) = st.top(); st.pop();

		//precisamos ver se existe caminho de custo k-peso_ate_araiz que termina na raiz atual
		int weight_needed = k-peso_ate_araiz;
		if(melhor.count(weight_needed)){
			ans = min(ans, melhor[weight_needed]+distancia_da_raiz);
		}
		
		//salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
		if(memoria.count(peso_ate_araiz)){
            memoria[peso_ate_araiz] = min(memoria[peso_ate_araiz], distancia_da_raiz);
        }else{
            memoria[peso_ate_araiz] = distancia_da_raiz;
        }

		//agora colocar os filhos na pilha
		for(int filho:adj[node]){
			if(filho != pai) st.push(make_tuple(filho, node, distancia_da_raiz+1, peso_ate_araiz+costs[node][filho]));
		}
	}
}

void resolve(vector<set<int>> &adj, int nodo, int k){
	vector<int> sub(adj.size(), 0);
    calcula_tam_subarvores(nodo, -1, adj, sub);
    int centroid = acha_centroide(nodo, -1, sub[nodo], adj, sub);

	unordered_map<int, int> melhor;
	melhor[0] = 0; //so fica no centroid e nao anda

	unordered_map<int, int> memoria;

	for(int filho:adj[centroid]){
        memoria.clear();
		dfs1(filho, centroid, adj, melhor, memoria, k);

		for(auto &par : memoria){
			int w   = par.first; //peso ate a raiz
			int dist = par.second; //distancia ate a raiz
			
            if(!melhor.count(w)){ //se nao tiver um melhor daquele peso
                melhor[w] = dist; //agora tem
            }else{
                melhor[w] = min(melhor[w], dist); //se tiver verifica se encontrou algum menos pesado
            }
		}
	}

    for(int filho : adj[centroid]) {
        adj[centroid].erase(filho);
        adj[filho].erase(centroid);
        resolve(adj, filho, k);
    }

	return;
}

int best_path(int N, int K, int H[][2], int L[]) {
    ans = INF;
    costs.clear();

    vector<set<int>> adj(N);
    for (int i = 0; i < N - 1; i++) {
        int u = H[i][0];
        int v = H[i][1];
        int w = L[i];

        adj[u].insert(v);
        adj[v].insert(u);

        costs[u][v] = w;
        costs[v][u] = w;
    }

    resolve(adj, 0, K);

    if(ans == INF){
        return -1;
    }else{
        return ans;
    }
}

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