Submission #964757

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

factories

#include <bits/stdc++.h>
 
#ifdef DEBUG
    #include <debug.hpp>
#else
    #define debug(...) 42
#endif
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
using namespace std;
 
const ll INF = 1e18;
 
vector<vector<pair<int, ll>>> gr;
vector<int> sz, used, act;
vector<ll> cls;
vector<vector<int>> cent;
vector<vector<ll>> dist;
int now = 0;
 
int find_sz(int v, int p) {
    sz[v] = 1;
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        sz[v] += find_sz(to, v);
    }
    return sz[v];
}
 
int centr(int v, int p, int cn) {
    bool flag = 1;
    while (flag) {
        flag = 0;
        for (auto [to, w] : gr[v]) {
            if (used[to] || to == p) continue;
            if (sz[to] > cn / 2) {
                p = v;
                v = to;
                flag = 1;
                break;
            }
        }
    }
    return v;
}
 
void dfs(int v, int c, int p = -1, ll d = 0) {
    cent[v].push_back(c);
    dist[v].push_back(d);
    assert(cent[v].size() <= 20);
    for (auto [to, w] : gr[v]) {
        if (used[to] || to == p) continue;
        dfs(to, c, v, d + w);
    }
} 
 
void Decomp(int v) {
    int cn = find_sz(v, v);
    int c = centr(v, v, cn); 
    used[c] = 1;
    dfs(c, c);
    for (auto [to, w] : gr[c]) {
        if (used[to]) continue;
        Decomp(to);
    }
}
 
void Init(int N, int A[], int B[], int D[]) {
    gr.assign(N, {}); 
    used.assign(N, 0);
    sz.assign(N, 0);
    cent.assign(N, {});
    dist.assign(N, {});
    cls.assign(N, INF);
    act.assign(N, 0);
    
    for (int i = 0; i < N; ++i) {
        gr[A[i]].emplace_back(B[i], D[i]);
        gr[B[i]].emplace_back(A[i], D[i]);
    }
 
    Decomp(0);
}
 
void Update(int v) {
    for (size_t j = 0; j < cent[v].size(); ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            cls[c] = min(cls[c], dist[v][j]);
        } else {
            cls[c] = dist[v][j]; 
            act[c] = now;
        }
    }
}
 
ll GetMin(int v) {
    ll res = INF;
    for (size_t j = 0; j < cent[v].size(); ++j) {
        int c = cent[v][j];
        if (act[c] == now) {
            res = min(res, dist[v][j] + cls[c]);
        }
    }
    return res;
}
 
ll Query(int S, int X[], int T, int Y[]) {
    // go through all X[i] centroids and update cls  
    for (int i = 0; i < S; ++i) {
        Update(X[i]);
    }
 
    // go through all Y[i] centroids and update min(res, dist[Y[i]][c] + cls[c])
    ll res = INF;
    for (int i = 0; i < T; ++i) {
        res = min(res, GetMin(Y[i])); 
    }
 
    // Update actuality
    ++now;
 
    return res;
}

int main() {
    int n, q;
    cin >> n >> q;
    
    vector<int> a(n), b(n), d(n);
    for (int i = 0; i < n - 1; ++i) {
        cin >> a[i] >> b[i] >> d[i];
    }

    Init(n, a.data(), b.data(), d.data());
    
    int s, t;
    for (int i = 0; i < q; ++i) {
        cin >> s >> t;
        vector<int> x(s), y(t);
        for (int j = 0; j < s; ++j) {
            cin >> x[j];
        }
        for (int j = 0; j < t; ++j) {
            cin >> y[j];
        }
        cout << Query(s, x.data(), t, y.data()) << "\n";
    }
}

Compilation message (stderr)

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