| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 62151 | Darksinian | Factories (JOI14_factories) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "factories.h"
#include<bits/stdc++.h>
#include"grader.cpp"
using namespace std;
int n;
int p[5002];
long long l[5002];
long long d[5002];
long long dp2[14][5002];
vector<pair<int,long long> > g[5002];
/*
void dfs(int s,int p) {
dp[s][1] = 1e17;
dp[s][2] = 1e17;
if(c[s]) dp[s][c[s]] = 0;
for(auto u : g[s]) {
int u1 = u.first;
if(u1!=p) {
dfs(u1,s);
dp[s][1] = min(dp[s][1],dp[u1][1] + u.second);
dp[s][2] = min(dp[s][2],dp[u1][2] + u.second);
}
}
}
*/
void dfs2(int s,int z) {
p[s] = z;
if(s==z) l[s] = 0;
else l[s] = l[z]+1;
for(auto u : g[s]) {
int u1 = u.first;
if(u1!=z) {
d[u1] = d[s] + u.second;
dfs2(u1,s);
}
}
}
int lca(int u,int v){
if(l[u] < l[v]) swap(u,v);
int len = l[u] - l[v];
for(int i =0;i<20;i++) {
if(len & (1<<i)) u = dp2[u][i];
}
if(u==v) return u;
for(int i =20;i>=0;i--) {
if(dp2[u][i] != dp2[v][i])
u = dp2[u][i],v = dp2[v][i];
}
return p[u];
}
int pre() {
for(int i =0;i<=20;i++){
for(int j =1;j<=n;j++){
if(!i) dp2[j][i] = p[j];
else dp2[j][i] = dp2[dp2[j][i-1]][i-1];
}
}
}
long long dist(int u, int v) {
return d[u] + d[v] - 2*d[lca(u,v)];
}
void Init(int N, int A[], int B[], int D[]) {
n = N;
for(int i =0;i<N;i++){
g[A[i]+1].push_back({B[i]+1,D[i]});
g[B[i]+1].push_back({A[i]+1,D[i]});
}
dfs2(1,1);
pre();
}
long long Query(int S, int X[], int T, int Y[]) {
for(int i =0;i<S;i++) {
//c[X[i]] = 1;
}
for(int i =0;i<T;i++){
//c[Y[i]] = 2;
}
//dfs(0,0);
// for(int i =0;i<n;i++) c[i] = 0;
long long ans = 1e18;
for(int i =0;i<S;i++) {
for(int j =0;j<T;j++) ans = min(ans,dist(X[i]+1,Y[j]+1));
}
return ans;
}