제출 #1317231

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1317231		h1drogen	공장들 (JOI14_factories)	C++17	컴파일 에러	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int INF = 1e18;
const int NMAX = 500500;

vector<pair<int,int>> g[NMAX];
int dp[NMAX], tin[NMAX], tout[NMAX], up[21][NMAX];
int sz[NMAX], par[NMAX], best[NMAX], us[NMAX];
int tim;

void dfs(int v,int p,int sum){
    tin[v]=tim++;
    dp[v]=sum;
    up[0][v]=p;
    for(int i=1;i<=20;i++)
        up[i][v]=up[i-1][up[i-1][v]];
    for(auto [to,c]:g[v]){
        if(to!=p)
            dfs(to,v,sum+c);
    }
    tout[v]=tim;
}

void precalc(int v,int p){
    sz[v]=1;
    for(auto [to,c]:g[v]){
        if(to!=p && !us[to]){
            precalc(to,v);
            sz[v]+=sz[to];
        }
    }
}

int get(int v,int p,int n){
    for(auto [to,_]:g[v]){
        if(sz[to]>n/2 && to!=p && !us[to])
            return get(to,v,n);
    }
    return v;
}

bool check(int a,int b){
    return tin[a]<=tin[b] && tout[b]<=tout[a];
}

int lca(int a,int b){
    if(check(a,b)) return a;
    if(check(b,a)) return b;
    for(int i=20;i>=0;i--){
        if(!check(up[i][a],b))
            a=up[i][a];
    }
    return up[0][a];
}

int dist(int a,int b){
    return dp[a]+dp[b]-2*dp[lca(a,b)];
}

void build(int v,int p){
    precalc(v,-1);
    int c=get(v,-1,sz[v]);
    us[c]=1;
    par[c]=p;
    for(auto k:g[c]){
        if(!us[k.first])
            build(k.first,c);
    }
}

void upd(int v,int x){
    best[v]=min(best[v],dist(v,x));
    if(par[v]<0) return;
    upd(par[v],x);
}

void nulify(int v){
    best[v]=INF;
    if(par[v]<0) return;
    nulify(par[v]);
}

int ans;
void res(int v,int x){
    ans=min(ans,dist(v,x)+best[v]);
    if(par[v]<0) return;
    res(par[v],x);
}

// === Батч API ===

void Init(int N, int A[], int B[], int D[]) {
    tim = 0;
    for(int i=0;i<=N;i++){
        g[i].clear();
        dp[i]=0;
        tin[i]=tout[i]=0;
        par[i]=-1;
        best[i]=INF;
        us[i]=0;
        sz[i]=0;
    }

    for(int i=0;i<N-1;i++){
        g[A[i]].push_back({B[i], D[i]});
        g[B[i]].push_back({A[i], D[i]});
    }

    dfs(0,0,0);
    build(0,-1);
    for(int i=0;i<N;i++) best[i]=INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i=0;i<S;i++)
        upd(X[i], X[i]);

    ans = INF;
    for(int i=0;i<T;i++)
        res(Y[i], Y[i]);

    for(int i=0;i<S;i++)
        nulify(X[i]);

    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccrVJF3T.o: in function `main':
grader.cpp:(.text.startup+0x3b0): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x43b): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status