oj.uz

Submission #975337

# Submission time Handle Problem Language Result Execution time Memory
975337 2024-05-04T19:48:31 Z aaaaaarroz Factories (JOI14_factories) C++17
18 / 100
 8000 ms 253228 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
vector<vector<pair<long long,long long>>> graph;

// depth[u] = la profundidad de u en el arbol (la raiz tiene profundidad 0)
vector<long long> depth;
vector<long long> costo;
// anc[u][i] = el ancestro 2^i de u (por ejemplo, anc[u][3] = el ancestro 8 de u)
vector<vector<long long>> anc;

void dfs(long long u, long long p, long long cost){
    depth[u] = depth[p] + 1;        // La profundidad de u es la profundidad de su padre + 1
    costo[u]=costo[p]+cost;
    anc[u][0] = p;                  // El ancestro 2^0 de u es su padre
    for(long long i = 1; i < 32; i++){    // Calculo todos los ancestros de u
        anc[u][i] = anc[anc[u][i-1]][i-1];
    }

    for(auto [v,w] : graph[u]){          // Visito todos los hijos de u (los vecinos excepto su padre)
        if(v != p){
            dfs(v, u, w);
        }
	}
}

// Sube dist niveles desde u en el arbol
long long lift(long long u, long long dist){
    for(long long i = 0; i < 32; i++){    
        if(dist & (1 << i)){
            u = anc[u][i];
        }
    }
    return u;
}

// Ancestro comun mas bajo de a y b
long long lca(long long a, long long b){
    if(depth[a] < depth[b]) swap(a, b); // Los ordeno de tal manera que a sea el mas profundo
    a = lift(a, depth[a] - depth[b]);   // Subo a a la misma profundidad que b
    if(a == b) return a;                // Si a y b son iguales, entonces a es el lca
    
    for(long long i = 31; i >= 0; i--){       // Subo a y b lo mas que pueda sin pasarme del lca
        if(anc[a][i] != anc[b][i]){
            a = anc[a][i];
            b = anc[b][i];
        }
    }
    return anc[a][0];                   // El lca es el padre de a
}

void Init(int N, int A[], int B[], int D[]){
	graph.resize(N,vector<pair<long long,long long>>());
    depth.resize(N,-1);
    costo.resize(N,0);
    anc.resize(N, vector<long long>(32));
	for(long long i=0;i<(N-1);i++){
		graph[A[i]].push_back({B[i],D[i]});
		graph[B[i]].push_back({A[i],D[i]});
	}
    dfs(0, 0, 0);
}

long long Query(int S, int X[], int T, int Y[]){
	long long ans=1e18;
	for(int i=0;i<S;i++){
		for(int j=0;j<T;j++){
			ans=min(ans,(costo[X[i]]-costo[lca(X[i],Y[j])])+(costo[Y[j]]-costo[lca(X[i],Y[j])]));
		}
	}
	return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16988 KB Output is correct
2 Execution timed out 8061 ms 32188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 2005 ms 232528 KB Output is correct
3 Correct 5316 ms 234896 KB Output is correct
4 Correct 1153 ms 229932 KB Output is correct
5 Correct 6276 ms 253228 KB Output is correct
6 Correct 4238 ms 236104 KB Output is correct
7 Correct 6031 ms 74212 KB Output is correct
8 Correct 1143 ms 73492 KB Output is correct
9 Correct 7769 ms 76776 KB Output is correct
10 Correct 3844 ms 74884 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16988 KB Output is correct
2 Execution timed out 8061 ms 32188 KB Time limit exceeded
3 Halted 0 ms 0 KB -