Submission #62222

#	Time	Username	Problem	Language	Result	Execution time	Memory
62222		Darksinian	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#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<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 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 =19;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[]) {

  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;
}

Compilation message (stderr)

factories.cpp: In function 'int pre()':
factories.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
/tmp/ccEmlmBc.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccLOa4E0.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status