oj.uz

Submission #62148

# Submission time Handle Problem Language Result Execution time Memory
62148 2018-07-27T13:57:12 Z Darksinian Factories (JOI14_factories) C++14
0 / 100
 187 ms 2808 KB 
#include "factories.h"
#include<bits/stdc++.h>
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 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]});
    }
}

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)];
}
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(1,1);
  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(X[i]+1,Y[j]+1));
  }
  return ans;
}

Compilation message

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

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Incorrect 187 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -