Submission #1271704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271704		ian_otoni	Race (IOI11_race)	C++20	100 / 100	291 ms	34280 KiB

race

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

using namespace std;

#define INF 999999999

vector<vector<pair<int, int>>> adj;
vector<bool> is_removed;
vector<pair<int, int>> melhor;
vector<int> sub;
int ans  = INF;
int flag = 1;

int calcula_tam_subarvores(int nodo, int pai){
    sub[nodo] = 1;
    for(auto &p : adj[nodo]){
        int filho = p.first;
        if(filho!=pai && !is_removed[filho]) sub[nodo] += calcula_tam_subarvores(filho, nodo);
    }

    return sub[nodo];
}

int acha_centroide(int nodo, int pai, int n){
    for(auto &p : adj[nodo]){
        int filho = p.first;
        if(filho!=pai && !is_removed[filho] && sub[filho]>n/2) return acha_centroide(filho, nodo, n);
    }

    return nodo;
}

void dfs1(int start_node, int parent_node, int k){
    
    stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso

    int initial_weight = 0;
    for(auto &edge : adj[start_node]){
        if(edge.first==parent_node){
            initial_weight = edge.second;
            break;
        }
    }

    st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //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(weight_needed>=0 && weight_needed<melhor.size()){ //nao negativo
            if(melhor[weight_needed].second==flag){
                ans = min(ans, melhor[weight_needed].first+distancia_da_raiz);
            }
		}

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

void dfs2(int start_node, int parent_node, int k){
	stack<tuple<int, int, int, int>> st; //nodo, pai, distancia e peso

    int initial_weight = 0;
    for(auto &edge : adj[start_node]){
        if(edge.first==parent_node){
            initial_weight = edge.second;
            break;
        }
    }

    st.push(make_tuple(start_node, parent_node, 1, initial_weight)); //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();

        if(peso_ate_araiz<0 || peso_ate_araiz>k){
            continue;
        }

		//salva os caminhos que comecam na raiz e terminam em vertices dessa subarvore
        if(melhor[peso_ate_araiz].second==flag){
            melhor[peso_ate_araiz].first = min(melhor[peso_ate_araiz].first, distancia_da_raiz);
        }else{ //primeira vez que este peso aparece
            melhor[peso_ate_araiz] = {distancia_da_raiz, flag};
        }

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

void resolve(int nodo, int k){
    calcula_tam_subarvores(nodo, -1);
    int centroid = acha_centroide(nodo, -1, sub[nodo]);

	melhor[0] = {0, flag}; //so fica no centroid e nao anda

	for(auto &p : adj[centroid]){
        int filho = p.first;
        if (!is_removed[filho]){
            dfs1(filho, centroid, k);
            dfs2(filho, centroid, k);
        }
	}

    is_removed[centroid] = true;
    flag++;

    for(auto &p : adj[centroid]){
        int filho = p.first;
        if(!is_removed[filho]){
            resolve(filho, k);
        }
    }

	return;
}

int best_path(int N, int K, int H[][2], int L[]) {
    ans = INF;
    flag = 1;

    adj.assign(N, vector<pair<int, int>>());
    is_removed.assign(N, false);
    melhor.assign(K+10, {0, 0});
    sub.assign(N, 0);

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

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    resolve(0, K);

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

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