Submission #532278

#	Time	Username	Problem	Language	Result	Execution time	Memory
532278		Pietra	Factories (JOI14_factories)	C++14	15 / 100	8037 ms	125592 KiB

factories

// tem uma arvore 
// cada companhia produz uma materia smp dif - cada uma tem no minimo
// uma industria, essa ficam nos vertices 
// pode ter mais de uma industria numa msm cidade 
// as vzs uma precisa de material da outra
// queremos minimizar a dist a ser percorrida ao precisar de uma materia da ind G
// query: a companhia u (com empresas em x1, x2,...) precisa
// de material da companhia v (com empresas em y1, y2, ...)
// qual a menor dist?
// lca + centroid 
// pega de um centroid p outro
// guarda o mais prox e p subir do vertice p centroide e de um p outro
// usa o lca pra pegar a dist 
// atualiza o centroid p cada empresa q lê
// vendo se ela cria um novo caminho minimo 
// pega o min entre oq ja ta e o min entre o vertice ate o cara k (centroid)
// na query queremos o minimo de ir ate o centroid atual e a menor 
// dist q ele tem pra algm empresa A 

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

const int maxn = 1e6 + 5 ; 
const ll inf = 1e17 ; 
const int maxl = 21 ; 

int tab[maxl][maxn], nivel[maxn], cent[maxn] ; 
long long dist[maxn], resp[maxn] ; 
int sz[maxn], pai[maxn], timer ;
bitset<maxn> vis ; 
int tin[maxn], tout[maxn] ;  
vector<pair<int,ll>> grafo[maxn] ; 

int anc(int a, int b){
	// b em a 
	return (tin[a] <= tin[b] && tout[a] >= tout[b]) ; 
}

int lca(int u, int v){ 

	if(anc(u, v)) return u ; 
	if(anc(v, u)) return v ; 

	for(int i = maxl - 1 ; i >= 0 ; i--){
		if(!anc(tab[i][v], u) && tab[i][v]) v = tab[i][v] ; 
	}

	return tab[0][v] ; 

}

ll find_dist(int a, int b){
	return dist[a] + dist[b] - ((dist[lca(a, b)])<<1) ; 
}

void update_cent(int u){

	int k = u ; 

	while(k){
		resp[k] = min(resp[k], find_dist(u, k)) ; 
		k = pai[k] ; 
 	}

}

void ini(int u){

	int k = u ; 

	while(k){
		resp[k] = inf ; k = pai[k] ; 
	}

}

ll query(int x){

	int k = x ; ll ans = inf ; 

	while(k){
		ans = min(ans, find_dist(x, k) + resp[k]) ; 
		k = pai[k] ; 
	}

	return ans ; 

}

long long Query(int S, int X[], int T, int Y[]) {

	ll ans = inf ; 

	for(int i = 0 ; i < S ; i++) update_cent(X[i] + 1) ; 

	for(int i = 0 ; i < T ; i++) ans = min(ans, query(Y[i] + 1)) ; 

	for(int i = 0 ; i < S ; i++) ini(X[i] + 1) ; 

	return ans ; 

}

void dfs_cent(int v, int p){

	sz[v] = 1 ; 

	for(auto a : grafo[v]){
		if(cent[a.first] || a.first == p) continue ; 
		dfs_cent(a.first, v) ; 
		sz[v] += sz[a.first] ; 
	}

}

int find_cent(int v, int p, int szz){

	for(auto a : grafo[v]){
		if(a.first == p || cent[a.first] || sz[a.first]*2 <= szz) continue ;
		return find_cent(a.first, v, szz) ;  
	}

	return v ; 

}

void make_cent(int v, int p){

	dfs_cent(v, p) ; 

	int c = find_cent(v, p, sz[v]) ; 
	cent[c] = 1, pai[c] = p ; 

	for(auto a : grafo[c]){
		if(cent[a.first]) continue ; 
		make_cent(a.first, c) ; 
	}

}

void dfs(int v, int p){

	vis[v] = 1 ; 
	tab[0][v] = p ; 

	tin[v] = ++timer ; 

	for(int i = 1 ; i < maxl ; i++) tab[i][v] = tab[i-1][tab[i-1][v]] ; 

	for(auto a : grafo[v]){
		if(vis[a.first] || a.first == p) continue ; 
		dist[a.first] = dist[v] + a.second ; 
		dfs(a.first, v) ; 
	}

	tout[v] = ++timer ; 

}

void Init(int N, int A[], int B[], int D[]) {
    
    for(int i = 0 ; i < N - 1 ; i++){
    	grafo[A[i]+1].push_back({B[i]+1, D[i]}) ; 
    	grafo[B[i]+1].push_back({A[i]+1, D[i]}) ; 
    }

    dfs(1, 0) ; make_cent(1, 0) ; 

    for(int i = 0 ; i < N + 1 ; i++) resp[i] = inf ; 

}

• Subtask 1: 15 / 15
• Subtask 2: 0 / 18
• Subtask 3: 0 / 67