제출 #1281752

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

factories

// 🌲🌲🌲🌲🌲🌳🌳🌳🌳🌳🌳🌴🌴🌴🌴🌴🌴🌴🌴
#include <bits/stdc++.h>
bool M1;
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;

#define MAXN 500005
#define MAXQ 100005
int n, q;
vector<pair<int, int>> g[MAXN];
bool blocked[MAXN];
int sz[MAXN];
int par[MAXN];
int dep[MAXN];
int sumWeight[MAXN];
int curWeight[MAXN];
int up[MAXN][20];
int bestVal[MAXN];
const int INF = 1e15;

///++++++++++++++++++++++++++++++++++++++///

void minimize(int &a, const int &b) {
    if (a > b) a = b;
}

void preCalc(int u, int p) {
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (v == p) continue;
        up[v][0] = u;
        dep[v] = dep[u] + 1;
        sumWeight[v] = sumWeight[u] + w;
        curWeight[v] = w;
        preCalc(v, u);
    }
}

void prepareLCA() {
    FOR(j, 1, 19) FOR(i, 1, n) {
        up[i][j] = up[up[i][j - 1]][j - 1];
    }
}

int LCA(int a, int b) {
    if (dep[a] < dep[b]) swap(a, b);
    int h = dep[a] - dep[b];
    for (int i = 0; (1 << i) <= h; ++i) {
        if (h >> i & 1) a = up[a][i];
    }
    if (a == b) return a;
    h = __lg(dep[a]);
    for (int i = h; i >= 0; --i) {
        if (up[a][i] != up[b][i]) {
            a = up[a][i];
            b = up[b][i];
        }
    }
    return up[a][0];
}

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

void calc(int u, int p) {
    sz[u] = 1;
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (blocked[v] || v == p) continue;
        calc(v, u);
        sz[u] += sz[v];
    }
}

int FindCentroid(int u, int p, int SZ) {
    for (pair<int, int> &x : g[u]) {
        int v, w; tie(v, w) = x;
        if (blocked[v] || v == p) continue;
        if (sz[v] > SZ) return FindCentroid(v, u, SZ);
    }
    return u;
}

void decompose(int curNode, int preCentroid) {
    calc(curNode, 0);
    int c = FindCentroid(curNode, 0, sz[curNode] / 2);
    par[c] = preCentroid;
    blocked[c] = true;
    for (pair<int, int> &x : g[c]) {
        int v, w; tie(v, w) = x;
        if (blocked[v]) continue;
        decompose(v, c);
    }
}

void update(int curNode) {
    int fixed = curNode;
    while (curNode != 0) {
        minimize(bestVal[curNode], dist(fixed, curNode));
        curNode = up[curNode][0];
    }
}

void reset(int curNode) {
    int fixed = curNode;
    while (curNode != 0) {
        bestVal[curNode] = 1e15;
        curNode = up[curNode][0];
    }
}

int query(int curNode) {
    int fixed = curNode;
    int res = INF;
    while (curNode != 0) {
        minimize(res, bestVal[curNode] + dist(curNode, fixed));
        curNode = up[curNode][0];
    }
    return res;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    FOR(i, 1, n - 1){
        int u = A[i - 1];
        int v = B[i - 1];
        int w = D[i - 1];
        u++;
        v++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    preCalc(1, 0);
    prepareLCA();
    decompose(1, 0);
    FOR(i, 1, n) bestVal[i] = 1e15;
}

long long Query(int S, int X[], int T, int Y[]) {
    vector<int> tmpNode;
    FOR(i, 1, S) {
        int curNode = X[i - 1];
        curNode++;
        update(curNode);
        tmpNode.push_back(curNode);
    }
    int res = INF;
    FOR(i, 1, T) {
        int curNode = Y[i - 1];
        curNode++;
        minimize(res, query(curNode));
    }
    for (int &curNode : tmpNode) reset(curNode);
    return res;
}

//void solve() {
//    cin >> n >> q;
//    FOR(i, 1, n - 1) {
//        int u, v, w; cin >> u >> v >> w;
//        u++; v++;
//        g[u].push_back({v, w});
//        g[v].push_back({u, w});
//    }
//    preCalc(1, 0);
//    prepareLCA();
//    decompose(1, 0);
//    FOR(i, 1, n) bestVal[i] = 1e15;
//    FOR(node1, 1, n) FOR(node2, 1, n) {
//        cerr << "test: " << node1 - 1 << ' ' << node2 - 1 << ' ' << dist(node1, node2) << '\n';
//    }
//    FOR(Nium, 1, q) {
//        int S, T; cin >> S >> T;
//        vector<int> tmpNode;
//        FOR(i, 1, S) {
//            int curNode; cin >> curNode;
//            curNode++;
//            update(curNode);
//            tmpNode.push_back(curNode);
//        }
//        int res = INF;
//        FOR(i, 1, T) {
//            int curNode; cin >> curNode;
//            curNode++;
//            minimize(res, query(curNode));
//        }
//        for (int &curNode : tmpNode) reset(curNode);
//        cout << res << '\n';
//    }
//}
//
///++++++++++++++++++++++++++++++++++++++///
//
//#define task "test"
//int32_t main() {
//    if (fopen(task".inp","r")) {
//        freopen(task".inp","r",stdin);
//        freopen(task".out","w",stdout);
//    }
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr); cout.tie(nullptr);
//    solve();
//    bool M2;
//    cerr << "++++++++++++++++++++++++++++\n";
//    cerr << "Time: " << clock() << "ms" << '\n';
//    cerr << "Memory: " << abs(&M2 - &M1) / 1024 / 1024 << "MB" << '\n';
//    cerr << "++++++++++++++++++++++++++++\n";
//    return 0;
//}

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

/usr/bin/ld: /tmp/ccmym6t1.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