Submission #236032

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

factories

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

const int N = 5e5;
vector<pair<int, long long>> adj[N];
int n, m;

vector<int> euler, depth;
int first[N], last[N], l2[N * 2], p2[N * 2];
long long dep[N];
int sparse[N * 2][22];
int c = 0;

int sub[N], par[N];
long long ans[N];
bool isCen[N];
int size = 0;

// LCA begins
void pre(int v, int p = -1, long long d = 0, int de = 0) {
    first[v] = c++;
    dep[v] = d;
    euler.push_back(v);
    depth.push_back(de);

    for (auto i : adj[v]) {
        if (i.first != p) {
            pre(i.first, v, d + i.second, de + 1);
            euler.push_back(v);
            depth.push_back(de);
            c++;
        }
    }

    last[v] = c - 1;
}

int merge(int a, int b) {
    return depth[a] < depth[b] ? a : b;
}

void build_sparse() {
    int es = euler.size();
    assert(es < N * 2);
    assert(l2[es] <= 22);
    for (int i = 0; i < es; i++)
        sparse[i][0] = i;

    for (int i = 1; i <= l2[es]; i++) {
        for (int j = 0; j < es && j - 1 + (p2[i]) < es; j++)
            sparse[j][i] = depth[sparse[j][i - 1]] < depth[sparse[j + (p2[i - 1])][i - 1]] ? sparse[j][i - 1] : sparse[j + (p2[i - 1])][i - 1];
    }
}

int lca(int u, int v) {
    if (u == v) return u;
    int f1 = min(first[u], first[v]), f2 = max(first[v], first[u]), diff = f2 - f1;
    int dx = l2[diff];
    return euler[merge(sparse[f1][dx], sparse[f2 - (p2[dx])][dx])];
}

long long dist(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}
// LCA ends

// Centroid decomposition begins
void calc(int v, int p = -1) { // Pre calculate subtree sizes
    sub[v] = 1;
    size++;
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[v])
            calc(i.first, v), sub[v] += sub[i.first];
    }
}

int find(int v, int p = -1) { // Find the centroid in current subtree
    for (auto i : adj[v]) {
        if (i.first != p && !isCen[i.first] && sub[i.first] > size / 2)
            return find(i.first, v);
    }
    return v;
}

void decompose(int v, int p = -1) {
    size = 0; // Stores size of current subtree
    calc(v);
    int centroid = find(v);
    par[centroid] = p;
    isCen[centroid] = true;

    for (auto i : adj[centroid]) {
        if (i.first != p && !isCen[i.first])
            decompose(i.first, centroid);
    }
}
// Centroid decomposition ends

void update(int v) {
    int p = v, co = 0;
    while (p != -1) {
        ans[p] = min(ans[p], dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
}

long long query(int v) {
    int p = v, co = 0;
    long long val = 1e18;
    while (p != -1) {
        val = min(val, ans[p] + dist(p, v));
        p = par[p];
    }
    assert(co <= 22);
    return val;
}

void revert(int v) {
    int p = v;
    while (p != -1) {
        ans[p] = 1e18;
        p = par[p];
    }
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i = 0; i < S; i++)
        update(X[i]);
    long long ans = 1e18;
    for (int i = 0; i < T; i++)
        ans = min(ans, query(Y[i]));
    for (int i = 0; i < S; i++)
        revert(X[i]);
    return ans;
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for (int i = 0; i < n - 1; i++) {
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }

    int val = 1,ptr=0;
    for (int i=1; i<1000000; i++)
    {
        l2[i] = ptr-1;
        if (val==i)
        {
            val*=2;
            l2[i] = ptr;
            ptr++;
        }
    }

    p2[0] = 1;
    for (int i = 1; i < min(N * 2, 30); i++)
        p2[i] = p2[i - 1] * 2;

    euler.reserve(N * 2);
    depth.reserve(N * 2);

    pre(0);
    build_sparse();
    decompose(0);
    fill(ans, ans + N, 1e18);
}

void solveTestCase() {
    int n, q;
    cin >> n >> q;

    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, b, d);

    for (int i = 0; i < q; i++) {
        int s, t;
        cin >> s >> t;

        int x[s], y[t];
        for (int &i : x)
            cin >> i;
        for (int &i : y)
            cin >> i;
        cout << Query(s, x, t, y) << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin >> test;
    while (test--)
        solveTestCase();
}

Compilation message (stderr)

/tmp/ccawztH8.o: In function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccHRgVC0.o:factories.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status