Submission #274869

#	Time	Username	Problem	Language	Result	Execution time	Memory
274869		smax	Factories (JOI14_factories)	C++17	100 / 100	7971 ms	224112 KiB

factories

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

#define MAXN 500005

const long long INF = 1e18;

struct CentroidDecomposition {
    vector<int> sub, par;
    vector<bool> visited;
    vector<vector<int>> adj;

    CentroidDecomposition() {}

    CentroidDecomposition(int n) : sub(n), par(n), visited(n), adj(n) {}

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void build(int u = 0, int p = -1) {
        u = centroid(u, p, dfs(u, p));
        par[u] = p;
        visited[u] = true;
        for (int v : adj[u])
            if (!visited[v])
                build(v, u);
    }

    int dfs(int u, int p) {
        sub[u] = 1;
        for (int v : adj[u])
            if (v != p && !visited[v])
                sub[u] += dfs(v, u);
        return sub[u];
    }

    int centroid(int u, int p, int sz) {
        for (int v : adj[u])
            if (v != p && !visited[v] && sub[v] > sz / 2)
                return centroid(v, u, sz);
        return u;
    }

    int operator [] (int i) const {
        return par[i];
    }
};

struct RMQ {
    vector<long long> a;
    vector<vector<int>> spt;

    void init(int n, long long *_a) {
        a.resize(n);
        spt.assign(1, vector<int>(n));
        for (int i=0; i<n; i++) {
            a[i] = _a[i];
            spt[0][i] = i;
        }

        for (int j=1; 1<<j<=n; j++) {
            spt.emplace_back(n - (1 << j) + 1);
            for (int i=0; i+(1<<j)<=n; i++) {
                if (a[spt[j-1][i]] < a[spt[j-1][i+(1<<(j-1))]])
                    spt[j][i] = spt[j-1][i];
                else
                    spt[j][i] = spt[j-1][i+(1<<(j-1))];
            }
        }
    }

    int query(int i, int j) {
        int k = 31 - __builtin_clz(j - i + 1);
        if (a[spt[k][i]] < a[spt[k][j-(1<<k)+1]])
            return spt[k][i];
        else
            return spt[k][j-(1<<k)+1];
    }
};

int idx, ti[MAXN], node[2*MAXN];
long long depth[2*MAXN];
vector<pair<int, int>> adj[MAXN];
RMQ rmq;

void dfs(int u, int p, long long d) {
    ti[u] = idx;
    node[idx] = u;
    depth[idx++] = d;
    for (auto &e : adj[u])
        if (e.first != p) {
            dfs(e.first, u, d + e.second);
            node[idx] = u;
            depth[idx++] = d;
        }
}

int lca(int u, int v) {
    if (ti[u] > ti[v])
        swap(u, v);
    return node[rmq.query(ti[u], ti[v])];
}

long long dist(int u, int v) {
    return depth[ti[u]] + depth[ti[v]] - 2 * depth[ti[lca(u, v)]];
}

void preprocess() {
    idx = 0;
    dfs(0, -1, 0);
    rmq.init(idx, depth);
}

long long ans[MAXN];
CentroidDecomposition cd;

void Init(int N, int A[], int B[], int D[]) {
    cd = CentroidDecomposition(N);
    for (int i=0; i<N-1; i++) {
        cd.addEdge(A[i], B[i]);
        adj[A[i]].emplace_back(B[i], D[i]);
        adj[B[i]].emplace_back(A[i], D[i]);
    }
    cd.build();
    preprocess();
    for (int i=0; i<N; i++)
        ans[i] = INF;
}

long long Query(int S, int X[], int T, int Y[]) {
    for (int i=0; i<S; i++) {
        int u = X[i];
        while (u != -1) {
            ans[u] = min(ans[u], dist(X[i], u));
            u = cd[u];
        }
    }
    long long ret = INF;
    for (int i=0; i<T; i++) {
        int u = Y[i];
        while (u != -1) {
            ret = min(ret, ans[u] + dist(Y[i], u));
            u = cd[u];
        }
    }
    for (int i=0; i<S; i++) {
        int u = X[i];
        while (u != -1) {
            ans[u] = INF;
            u = cd[u];
        }
    }
    return ret;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67