Submission #531941

#TimeUsernameProblemLanguageResultExecution timeMemory
531941PietraFactories (JOI14_factories)C++14
0 / 100
23 ms24324 KiB
// 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 int long long using namespace std; const int maxn = 1e6 + 5 ; const int inf = 1e18 ; const int maxl = 22 ; int tab[maxl][maxn], dist[maxn], nivel[maxn], cent[maxn] ; int sz[maxn], vis[maxn], pai[maxn], timer, resp[maxn] ; int tin[maxn], tout[maxn] ; vector<pair<int,int>> grafo[maxn] ; void dfs(int v, int p){ tab[0][v] = p ; vis[v] = 1 ; tin[v] = ++timer ; for(auto a : grafo[v]){ if(a.first == p || vis[a.first]) continue ; nivel[a.first] = nivel[v] + 1 ; dist[a.first] = dist[v] + a.second ; dfs(a.first, v) ; } tout[v] = ++timer ; } int anc(int a, int b){ // b na arv de 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], v) && tab[i][v]) v = tab[i][v] ; } return tab[0][v] ; } int find_dist(int a, int b){ return dist[a] + dist[b] - 2LL*(dist[lca(a, b)]) ; } void dfs_cent(int v, int p){ sz[v] = 1 ; for(auto a : grafo[v]){ if(a.first == p || cent[a.first]) 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] || 2*sz[a.first] <= 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] || a.first == c) continue ; make_cent(a.first, c) ; } } 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] ; } } int query(int x){ int k = x ; int ans = inf ; while(k){ ans = min(ans, find_dist(x, k) + resp[k]) ; // ir ate o cent + dist empresa prox k = pai[k] ; } return ans ; } long long Query(int32_t S, int32_t X[], int32_t T, int32_t Y[]) { int ans = inf ; // min resp for(int i = 0 ; i < S ; i++) update_cent(X[i]+1) ; // menor dist p cada centroid de Xi for(int i = 0 ; i < T ; i++) ans = min(ans, query(Y[i]+1)) ; // menor dist usando a empresa yi for(int i = 0 ; i < S ; i++) ini(X[i]+1) ; // voltar com o val do ini return ans ; } void Init(int32_t N, int32_t A[], int32_t B[], int32_t D[]) { int n = N ; 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 = 1 ; i < maxl ; i++){ for(int j = 1 ; j <= n ; j++){ if(!tab[i-1][j]) continue ; tab[i][j] = tab[i-1][tab[i-1][j]] ; } } // for(int i = 1 ; i <= n ; i++) cout << dist[i] << " " << nivel[i] << "\n" ; for(int i = 0 ; i <= n ; i++) resp[i] = inf ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...