Submission #881549

#	Time	Username	Problem	Language	Result	Execution time	Memory
881549		Beerus13	Factories (JOI14_factories)	C++14	Compilation error	0 ms	0 KiB

factories

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int ar = 5e5 + 5;

int n, q, N;
int sz[ar], parent[ar];
multiset<ll> se[ar];
vector<int> adj[ar];
bool deleted[ar];
unordered_map<int, ll> dis[ar];
int vt[ar];

void dfs(int u, int par) {
    ++N;
    sz[u] = 1;
    for(auto x : adj[u]) if(x != par && !deleted[x]) {
        dfs(x, u);
        sz[u] += sz[x];
    }
}

int find_centroid(int u, int par) {
    for(auto x : adj[u]) if(x != par && !deleted[x] && sz[x] > N / 2) return find_centroid(x, u);
    return u;
}

void build_distance(int u, int par, int c, ll d) {
    dis[c][u] = d;
    for(auto x : adj[u]) if(x != par && !deleted[x]) build_distance(x, u, c, d + dis[u][x]);
}

void build_tree(int u, int par) {
    N = 0;
    dfs(u, par);
    int centroid = find_centroid(u, par);
    parent[centroid] = par;
    deleted[centroid] = 1;
    build_distance(centroid, par, centroid, 0);
    for(int x : adj[centroid]) if(x != parent[centroid] && !deleted[x]) build_tree(x, centroid);
}

void add(int u) {
    for(int par = u; par; par = parent[par]) se[par].insert(dis[par][u]);
}

void del(int u) {
    for(int par = u; par; par = parent[par]) se[par].erase(se[par].find(dis[par][u]));
}

ll get(int u) {
    ll Min = 1e18;
    for(int par = u; par; par = parent[par]) {
        if(se[par].size()) Min = min(Min, dis[par][u] + *se[par].begin());
    }
    return Min;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i < n; ++i) {
        int x, y, w; cin >> x >> y >> w;
        x++; y++;
        adj[x].push_back(y);
        adj[y].push_back(x);
        dis[x][y] = dis[y][x] = w;
    }
    build_tree(1, 0);
    while(q--) {
        int a, b; cin >> a >> b;
        for(int i = 1; i <= a; ++i) {
            cin >> vt[i];
            vt[i]++;
            add(vt[i]);
        }
        ll ans = 1e18;
        for(int i = 1; i <= b; ++i) {
            int u; cin >> u;
            u++;
            ans = min(ans, get(u));
        }
        for(int i = 1; i <= a; ++i) del(vt[i]);
        cout << ans << '\n';
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccMO9vML.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/cc68fNiL.o:factories.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccMO9vML.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