| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 62264 | 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[500002];
int l[500002];
int c[500002];
long long d[500002];
int dp2[500002][20];
long long dp[500002][3];
vector<int> E;
int ind[1000002];
int org[1000002];
int L[1000006];
int dp3[1000002][20];
int occ[1000002];
vector<pair<int,long long> > g[500002];
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 vis[500002];
void bfs() {
queue<int> q;
q.push(1);
int in = 0;
while(!q.empty()) {
in++;
int v = q.front();
ind[v] = in;
org[in] = v;
q.pop();
vis[v] = 1;
for(auto u : g[v]) {
if(u.first!=v && !vis[u.first]) {
q.push(u.first);
}
}
}
}
void dfs3(int s,int p) {
E.push_back(ind[s]);
occ[s] = E.size()-1;
for(auto u : g[s]) {
if(u.first!=p) {
dfs3(u.first,s);
E.push_back(ind[s]);
}
}
}
void pre2() {
for(int i =0;i<20;i++){
for(int j =0;j<E.size();j++){
dp3[j][i] = INT_MAX;
}
}
for(int i =0;i<20;i++){
for(int j =0;j+(1<<i)-1<E.size();j++){
if(!i) dp3[j][i] = E[j];
else dp3[j][i] = min(dp3[j][i-1],dp3[j + (1<<(i-1)) ][i-1]);
}
}
}
int qr(int l,int r) {
int k = 31 - __builtin_clz(r-l+1);
return min(dp3[l][k],dp3[r-(1<<k)+1][k]);
}
void pretree() {
bfs();
dfs3(1,1);
pre2();
}
int lca(int u,int v){
int ll = occ[u];
int r = occ[v];
int lc = qr(min(ll,r),max(ll,r));
return org[lc];
if(l[u] < l[v]) swap(u,v);
int len = l[u] - l[v];
for(int i =0;i<19;i++) {
if(len & (1<<i)) u = dp2[u][i];
}
if(u==v) return u;
for(int i =18;i>=0;i--) {
if(dp2[u][i] != dp2[v][i])
u = dp2[u][i],v = dp2[v][i];
}
return p[u];
}
void pre() {
for(int i =0;i<19;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]});
}
for(int i =1,j =0;i<1000005;i*=2,j++) L[i] = j;
for(int i =2;i<1000005;i++) {
if(!L[i]) L[i] = L[i-1];
}
dfs2(1,1);
pre();
pretree();
}
long long Query(int S, int X[], int T, int Y[]) {
long long ans = 1e18;
if(!(S<=10 && T<=10)) {
for(int i =0;i<S;i++) {
c[X[i]+1] = 1;
}
for(int i =0;i<T;i++){
c[Y[i]+1] = 2;
}
dfs(1,1);
for(int i =1;i<=n;i++) c[i] = 0;
for(int i =1;i<=n;i++) {
ans = min(ans,dp[i][2] + dp[i][1]);
}
}
else {
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;
}