Submission #1292103

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

factories

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
const int B = 1000;
const int LOG = 20;
vector<array<int, 2>>G[N];
int tin[N], tout[N], TIME = 0, up[LOG][N];
long long d[N];
void dfs(int node, int par){
    tin[node] = ++TIME;
    up[0][node] = par;
    for(auto &[v, w] : G[node]){
        if(v == par)continue;
        d[v] = d[node] + w;
        dfs(v, node);
    }
    tout[node] = TIME;
}
bool isAncestor(int u, int v){
    return (tin[u] <= tin[v] && tout[v] <= tout[u]);
}
int LCA(int u, int v){
    if(isAncestor(u, v))return u;
    for(int i = LOG - 1;i >= 0;--i){
        if(!isAncestor(up[i][u], v)){
            u = up[i][u];
        }
    }
    return up[0][u];
}
long long dist(int u, int v){
    return d[u] + d[v] - 2 * d[LCA(u, v)];
}
void Init(int N, int A[], int B[], int D[]){
    for(int i = 0;i < N - 1;++i){
        G[A[i]].push_back({B[i], D[i]});
        G[B[i]].push_back({A[i], D[i]});
    }
    dfs(0, 0);
    for(int i = 1;i < LOG;++i){
        for(int j = 0;j < N;++j){
            up[i][j] = up[i - 1][up[i - 1][j]];
        }
    }
}
long long Query(int S, int X[], int T, int Y[]){
    long long mn = 1e18;
    if(S >= B){
        vector<long long>dist2(N, 1e18);
        priority_queue<array<long long, 2>>pq;
        for(int i = 0;i < S;++i){
            dist2[X[i]] = 0;
            pq.push({dist2[X[i]], X[i]});
        }
        while(!pq.empty()){
            long long d1 = -pq.top()[0], node = pq.top()[1];
            pq.pop();
            if(d1 != dist2[node])continue;
            for(auto &[v, w] : G[node]){
                if(dist2[v] > dist2[node] + w){
                    dist2[v] = dist2[node] + w;
                    pq.push({-dist2[v], v});
                }
            }
        }
        for(int i = 0;i < T;++i){
            mn = min(mn, dist2[Y[i]]);
        }
    }
    else{
        for(int i = 0;i < S;++i){
            for(int j = 0;j < T;++j){
                mn = min(mn, dist(X[i], Y[j]));
            }
        }
    }
    return mn;
}   
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    int a[n - 1], b[n - 1], d[n - 1];
    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;
        int x[s], y[t];
        for(int i = 0;i < s;++i){
            cin >> x[i];
        }
        for(int i = 0;i < t;++i){
            cin >> y[i];
        }
        cout << Query(s, x, t, y) << '\n';
    }
}

Compilation message (stderr)

/usr/bin/ld: /tmp/ccqY5PWa.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccppDbQo.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status