Submission #62137

#	Time	Username	Problem	Language	Result	Execution time	Memory
62137		Darksinian	Factories (JOI14_factories)	C++14	0 / 100	21 ms	6136 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
using namespace std;
long long dp[100002][3];
int c[100002];
int n;
int p[100002];
long long l[100002];
long long d[100002];
long long dp2[21][100002];
vector<pair<int,int> > g[100002];
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 Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i =0;i<N;i++){
        g[A[i]].push_back({B[i],D[i]});
        g[B[i]].push_back({A[i],D[i]});
    }
}

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 ll = l[v] - l[u];
for(int i =0;i<20;i++){
    if(ll & (1<<i) ) v = dp2[v][i];
}
if(v == u) return v;
for(int i =20;i>-1;i--){
    if(dp2[v][i] != dp2[u][i] && dp2[v][i] !=-1) {
        v = dp2[v][i];
        u = dp2[u][i];
    }
}
return p[v];
}

int pre() {
   for(int i =0;i<=20;i++){
     for(int j =0;j<n;j++){
        if((1<<i) > l[j]) {
            dp2[j][i] = -1;
            continue;
        }
        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 l[u] + l[v] - 2*l[lca(u,v)];
}
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);
  dfs2(0,0);
  pre();
 // 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(i,j));
  }
  return ans;
}

Compilation message (stderr)

factories.cpp: In function 'int pre()':
factories.cpp:73:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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