Submission #853785

#	Time	Username	Problem	Language	Result	Execution time	Memory
853785		anha3k25cvp	Factories (JOI14_factories)	C++14	100 / 100	4990 ms	283392 KiB

factories

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define dl double
#define st first
#define nd second
#define II pair <int, int>
#include "factories.h"

using namespace std;

const ll inf = 7 + 1e18;

int n, logn, tsize;
vector <int> sz, pa, h;
vector <ll> f, ans;
vector <vector <int>> p;
vector <vector <II>> adj;

///--------------------------LCA-------------------------------

void dfs_lca(int u) {
    for (auto z : adj[u]) {
        int v = z.st;
        ll w = z.nd;
        if (h[v])
            continue;
        h[v] = h[u] + 1;
        f[v] = f[u] + w;
        p[0][v] = u;
        dfs_lca(v);
    }
}

int lca(int u, int v) {
    if (h[u] < h[v])
        swap(u, v);
    int d = h[u] - h[v];
    for (int si = d; si > 0; si ^= si & -si) {
        int i = __builtin_ctz(si & -si);
        u = p[i][u];
    }
    if (u == v)
        return u;
    for (int i = logn - 1; i >= 0; i --)
        if (p[i][u] != p[i][v]) {
            u = p[i][u];
            v = p[i][v];
        }
    return p[0][u];
}

ll dis(int u, int v) {
    return f[u] + f[v] - f[lca(u, v)] * 2;
}

///-------------------------CENTROID-----------------------------

void dfs(int u, int p) {
    tsize ++;
    sz[u] = 1;
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        dfs(v, u);
        sz[u] += sz[v];
    }
}

int centroid(int u, int p) {
    for (auto z : adj[u]) {
        int v = z.st;
        if (v == p || pa[v])
            continue;
        if (sz[v] * 2 > tsize)
            return centroid(v, u);
    }
    return u;
}

void build(int u, int p) {
    tsize = 0;
    dfs(u, 0);
    int c = centroid(u, 0);
    if (p == 0)
        pa[c] = c;
    else
        pa[c] = p;
    for (auto z : adj[c]) {
        int v = z.st;
        if (pa[v])
            continue;
        build(v, c);
    }
}

vector <vector <ll>> dist;

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    adj.resize(n + 1);
    for (int i = 0; i < n - 1; i ++) {
        A[i] ++; B[i] ++;
        adj[A[i]].push_back({B[i], D[i]});
        adj[B[i]].push_back({A[i], D[i]});
    }
    for (logn = 1; (1 << logn) <= n; logn ++);
    h.assign(n + 1, 0);
    p.assign(logn, vector <int> (n + 1, 0));
    f.assign(n + 1, 0);
    h[1] = 1;
    dfs_lca(1);
    for (int i = 1; i < logn; i ++)
        for (int u = 1; u <= n; u ++)
            p[i][u] = p[i - 1][p[i - 1][u]];
    sz.assign(n + 1, 0);
    pa.assign(n + 1, 0);
    build(1, 0);
    ans.assign(n + 1, inf);
    dist.resize(n + 1);
    for (int u = 1; u <= n; u ++)
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            dist[u].push_back(dis(v, u));
        }
}

long long Query(int S, int X[], int T, int Y[]) {
    vector <int> del;
    ll res = inf;
    for (int i = 0; i < S; i ++) {
        int u = X[i] + 1, cnt = 0;
        if (ans[u] == inf)
            del.push_back(u);
        ans[u] = 0;
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            if (ans[v] == inf)
                del.push_back(v);
            ans[v] = min(ans[v], dist[u][cnt]);
            del.push_back(v);
            cnt ++;
        }
    }
    for (int i = 0; i < T; i ++) {
        int u = Y[i] + 1, cnt = 0;
        res = min(res, ans[u]);
        for (int v = u; v != pa[v]; ) {
            v = pa[v];
            res = min(res, dist[u][cnt] + ans[v]);
            cnt ++;
        }
    }
    for (int u : del)
        ans[u] = inf;
    return res;
}

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