Submission #1110908

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110908		LucasLe	Factories (JOI14_factories)	C++17	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
#define int long long

const int maxn = 5e5 + 5;
const int LG = 19;
const int INF = 1e17;

int n, q, timeDfs;
int sparse[maxn + 5][LG + 5], par[maxn + 5];
int d[maxn + 5], lg[maxn + 5], sz[maxn + 5], depth[maxn + 5], h[maxn + 5], tin[maxn + 5];

bool del[maxn + 5];
std::vector<std::pair<int, int>> g[maxn + 5];

void init() {
    for (int i = 2; i <= maxn; ++i)
        lg[i] = lg[i / 2] + 1;
}

int combine(int u, int v) {
    return h[u] < h[v] ? u : v;
}

void dfs(int u, int p) {
    sparse[++timeDfs][0] = u;
    tin[u] = timeDfs;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        int w = tmp.second;
        if (v == p) continue;
        depth[v] = depth[u] + w;
        h[v] = h[u] + 1;
        dfs(v, u);
        sparse[++timeDfs][0] = u; 
    }
}

int find_centroid(int u, int p, int m) {
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        if (sz[v] > m / 2) return find_centroid(v, u, m);
    }
    return u;
}

void reset_sz(int u, int p) {
    sz[u] = 1;
    for (std::pair<int, int> tmp : g[u]) {
        int v = tmp.first;
        if (del[v] || v == p) continue;
        reset_sz(v, u);
        sz[u] += sz[v];
    }
}

int dist(int u, int v) {
    if (tin[u] > tin[v]) std::swap(u, v);
    int base = lg[tin[v] - tin[u] + 1];
    int lca = combine(sparse[tin[u]][base], sparse[tin[v] - (1 << base) + 1][base]);
    return depth[u] + depth[v] - 2 * depth[lca];
}

int CD(int u) {
    reset_sz(u, 0);
    int cen = find_centroid(u, 0, sz[u]);
    del[cen] = true;
    for (std::pair<int, int> tmp : g[cen]) {
        int v = tmp.first;
        if (del[v]) continue;
        par[CD(v)] = cen;
    }
    return cen;
}

void update(int u) {
    int anc = u;
    while (anc) {
        d[anc] = std::min(d[anc], dist(u, anc));
        anc = par[anc];
    }
}

int query(int u) {
    int anc = u;
    int ans = INF;
    while (anc) {
        ans = std::min(ans, dist(u, anc) + d[anc]);
        anc = par[anc];
    }
    return ans;
}

void init_d(int u) {
    int anc = u;
    while (anc) {
        d[anc] = INF;
        anc = par[anc];
    }
}

void solve() {
    std::cin >> n >> q;
    for (int i = 1, u, v, w; i < n; ++i) {
        std::cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    dfs(1, 0);
    for (int j = 1; j <= LG; ++j) {
        for (int i = 1; i <= timeDfs; ++i) {
            sparse[i][j] = combine(sparse[i][j - 1], sparse[i + (1 << (j - 1))][j - 1]);
        }
    }
    CD(1);
    for (int i = 1; i <= n; ++i) d[i] = INF;
    std::vector<int> nd;
    for (int _ = 1; _ <= q; ++_) {
        int sn, sm; std::cin >> sn >> sm;
        for (int i = 1; i <= sn; ++i) {
            int u; std::cin >> u;
            nd.push_back(u);
            update(u);
        }
        int ans = INF;
        for (int i = 1; i <= sm; ++i) {
            int u; std::cin >> u;
            ans = std::min(ans, query(u));
        }
        std::cout << ans << '\n';
        for (int u : nd) 
            init_d(u);
        nd.clear();
    }
}   

signed main() {
    std::ios_base::sync_with_stdio(false);  
    std::cin.tie(0);

    int tc = 1;
    // std::cin >> tc;
    init();
    while (tc--) {
        solve();
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccwzZw1B.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccCik2bC.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccwzZw1B.o: in function `main':
grader.cpp:(.text.startup+0x37d): undefined reference to `Init(int, int*, int*, int*)'
/usr/bin/ld: grader.cpp:(.text.startup+0x412): undefined reference to `Query(int, int*, int, int*)'
collect2: error: ld returned 1 exit status