제출 #1209130

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209130		DangKhoizzzz	Factories (JOI14_factories)	C++20	컴파일 에러	0 ms	0 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair <int , int>
#define arr3 array <int , 3>

using namespace std;

const int INF = 1e18;
const int maxn = 1e6 + 7;

bool del[maxn];
int n, dep[maxn], pos[maxn], log_2[maxn], parent[maxn], child[maxn], dp[maxn];
vector <pii> g[maxn];
vector <int> node = {-1};
pii mindep[20][maxn];

void dfs(int u, int p)
{
    node.push_back(u);
    for(pii e: g[u])
    {
        int v = e.fi, w = e.se;
        if(v == p) continue;
        dep[v] = dep[u] + w;
        dfs(v, u);
        node.push_back(u);
    }
}

int LCA(int u, int v)
{
    int l = pos[u], r = pos[v];
    if(l > r) swap(l, r);
    int k = log_2[r - l + 1];
    pii ss = min(mindep[k][l], mindep[k][r-(1 << k)+1]);
    return ss.se;
}

int dist(int u, int v)
{
    return dep[u] + dep[v] - 2*dep[LCA(u, v)];
}

void count_child(int u, int p)
{
    child[u] = 1;
    for(pii e: g[u])
    {
        int v = e.fi;
        if(v == p || del[v]) continue;
        count_child(v, u);
        child[u] += child[v];
    }
}

int centroid(int u, int p, int sz)
{
    for(pii e: g[u])
    {
        int v = e.fi;
        if(v == p || del[v]) continue;
        if(child[v] > sz/2) return centroid(v, u, sz);
    }
    return u;
}

void decompose(int u, int last)
{
    count_child(u, u);
    int root = centroid(u, u, child[u]);
    del[root] = 1;
    parent[root] = last;

    for(pii e: g[root])
    {
        int v = e.fi;
        if(!del[v]) decompose(v, root);
    }
}

void build()
{
    dfs(1, 0);
    for(int i = 1; i <= 2*n - 1; i++)
    {
        if(i > 1) log_2[i] = log_2[i/2] + 1;
        mindep[0][i] = {dep[node[i]], node[i]};
        pos[node[i]] = i;
    }
    for(int j = 1; j < 20; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= 2*n - 1; i++)
        {
            mindep[j][i] = min(mindep[j-1][i], mindep[j-1][i + (1 << (j-1))]);
        }
    }
    decompose(1, 0);
    for(int i = 1; i <= n; i++) dp[i] = INF;
}


void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n-1; i++)
    {
        int u = A[i], v = B[i], w = D[i];
        u++, v++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    build();
}

void UPDATE(int u)
{
    int p = u;
    while(p != 0)
    {
        dp[p] = min(dp[p], dist(u, p));
        p = parent[p];
    }
}

void REMOVE(int u)
{
    while(u != 0)
    {
        dp[u] = INF;
        u = parent[u];
    }
}

int ASK(int u)
{
    int ans = INF, p = u;
    while(p != 0)
    {
        ans = min(ans, dp[p] + dist(u, p));
        p = parent[p];
    }
    return ans;
}

long long Query(int S, int X[], int T, int Y[])
{
    int ans = INF;
    for(int i = 0; i < S; i++) UPDATE(X[i]+1);
    for(int i = 0; i < T; i++) ans = min(ans, ASK(Y[i]+1));
    for(int i = 0; i < S; i++) REMOVE(X[i]+1);
    return ans;
}


void solve()
{
    int N, Q;
    cin >> N >> Q;
    int A[N], B[N], D[N];
    for(int i = 0; i < N - 1; i++) cin >> A[i] >> B[i] >> D[i];
    Init(N, A, B, D);

    while(Q--)
    {
        int s , t;
        cin >> s >> t;
        for (int i = 0; i < s; ++i) cin >> A[i];
        for (int i = 0; i < t; ++i) cin >> B[i];
        cout << Query(s, A, t, B) << "\n";
    }
}

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

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