Submission #1265966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265966		icebear	Factories (JOI14_factories)	C++20	Compilation error	0 ms	0 KiB

factories

// ~~ icebear ~~
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

template<class T>
    bool minimize(T &a, const T &b) {
        if (a > b) return a = b, true;
        return false;
    }

template<class T>
    bool maximize(T &a, const T &b) {
        if (a < b) return a = b, true;
        return false;
    }

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORR(i,a,b) for(int i=(a); i>=(b); --i)
#define REP(i, n) for(int i=0; i<(n); ++i)
#define RED(i, n) for(int i=(n)-1; i>=0; --i)
#define MASK(i) (1LL << (i))
#define BIT(S, i) (((S) >> (i)) & 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define task "icebear"

const int MOD = 1e9 + 7;
const int inf = 1e9 + 27092008;
const ll INF = 1e18 + 27092008;
const int N = 5e5 + 5;
int n;
vector<ii> G[N];
int par[N], sz[N], minHigh[20][N << 1], pos[N], tour[N << 1], timer = 0, h[N];
ll f[N];

void prepare(int u, int par) {
    pos[u] = ++timer;
    tour[timer] = u;
    for(ii v : G[u]) if (v.fi != par) {
        h[v.fi] = h[u] + 1;
        f[v.fi] = f[u] + v.se;
        prepare(v.fi, u);
        tour[++timer] = u;
    }
}

#define MIN_HIGH(x, y) (h[x] < h[y] ? x : y)
int LCA(int u, int v) {
    int l = pos[u], r = pos[v];
    if (l > r) swap(l, r);
    int k = __lg(r - l + 1);
    return MIN_HIGH(minHigh[l][k], minHigh[r - MASK(k) + 1][k]);
}

ll dist(int u, int v) {
    int p = LCA(u, v);
    return f[u] + f[v] - 2 * f[p];
}

bool isCentroid[N];
int calc_sz(int u, int par) {
    sz[u] = 1;
    for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi])
        sz[u] += calc_sz(v.fi, u);
    return sz[u];
}

int findCentroid(int u, int par, const int &S) {
    for(ii v : G[u]) if (v.fi != par && !isCentroid[v.fi] && sz[v.fi] * 2 > S)
        return findCentroid(v.fi, u, S);
    return u;
}

void buildCentroid(int u, int pre) {
    int centroid = findCentroid(u, -1, calc_sz(u, -1));
    isCentroid[centroid] = true;
    par[centroid] = pre;

    for(ii v : G[centroid]) if (!isCentroid[v.fi])
        buildCentroid(v.fi, centroid);
}

ll minDist[N];
void Init(int N, vector<int> A, vector<int> B, vector<int> D) {
    n = N;
    REP(i, N - 1) {
        G[A[i]].pb(mp(B[i], D[i]));
        G[B[i]].pb(mp(A[i], D[i]));
    }
    prepare(0, -1);
    FOR(i, 1, timer) minHigh[i][0] = tour[i];
    FOR(j, 1, 19) FOR(i, 1, timer - MASK(j) + 1)
        minHigh[i][j] = MIN_HIGH(minHigh[i][j - 1], minHigh[i + MASK(j - 1)][j - 1]);
    buildCentroid(0, -1);
    memset(minDist, 0x3f, sizeof minDist);
}

void update(int u) {
    int node = u;
    while(node >= 0) {
        minimize(minDist[node], dist(u, node));
        node = par[node];
    }
}

void set_off(int u) {
    int node = u;
    while(node > 0) {
        minDist[node] = INF;
        node = par[node];
    }
}

ll getMin(int u) {
    ll ans = INF;
    int node = u;
    while(node > 0) {
        minimize(ans, minDist[node] + dist(u, node));
        node = par[node];
    }
    return ans;
}

ll Query(int S, vector<int> X, int T, vector<int> Y) {
    for(int &u : X) update(u);
    ll ans = INF;
    for(int &v : Y) minimize(ans, getMin(v));
    for(int &u : X) set_off(u);
    return ans;
}

// int main() {
//     Init(7, {0, 1, 2, 2, 4, 1}, {1, 2, 3, 4, 5, 6}, {4, 4, 5, 6, 5, 3});
//     cout << Query(2, {0, 6}, 2, {3, 4}) << ' ' << Query(3, {0, 1, 3}, 2, {4, 6}) << ' ' << Query(1, {2}, 1, {5});
//     return 0;
// }

Compilation message (stderr)

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