Submission #304597

#	Time	Username	Problem	Language	Result	Execution time	Memory
304597		kenechi	Factories (JOI14_factories)	C++14	15 / 100	2349 ms	323328 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define maxn 100010
const int MOD = 1000000007;


struct lca_lift {
    const int lg = 24;
    int n;
    vector<int> depth;
    vector<long long> val;
    vector<vector<pair<int, int>>> edges;
    vector<vector<int>> lift;

    void init(int sz) {
        n = sz + 1;
        depth = vector<int>(n);
        val = vector<long long>(n);
        edges = vector<vector<pair<int, int>>>(n, vector<pair<int, int>>());
        lift = vector<vector<int> >(n, vector<int>(lg, -1));
    }

    void edge(int a, int b, int w) {
        edges[a].push_back({b, w});
        edges[b].push_back({a, w});
    }

    void init_lift(int v = 1) {
        depth[v] = val[v] = 0;
        dfs(v, -1);
    }

    void dfs(int v, int par) {
        lift[v][0] = par;

        for (int i = 1; i < lg; i++) {
            if (lift[v][i - 1] == -1) lift[v][i] = -1;
            else lift[v][i] = lift[lift[v][i - 1]][i - 1];
        }

        for (auto x: edges[v]) {
            if (x.first != par) {
                val[x.first] = x.second + val[v];
                depth[x.first] = depth[v] + 1;
                dfs(x.first, v);
            }
        }
    }

    int get(int v, int k) {
        for (int i = lg - 1; i >= 0; i--) {
            if (v == -1) return v;
            if ((1 << i) <= k) {
                v = lift[v][i];
                k -= (1 << i);
            }
        }
        return v;
    }

    int get_lca(int a, int b) {
        if (depth[a] < depth[b]) swap(a, b);
        int d = depth[a] - depth[b];
        int v = get(a, d);
        if (v == b) {
            return v;
        } else {
            for (int i = lg - 1; i >= 0; i--) {
                if (lift[v][i] != lift[b][i]) {
                    v = lift[v][i];
                    b = lift[b][i];
                }
            }
            return lift[b][0];
        }
    }

    long long get_dist(int a, int b) {
        long long v = get_lca(a, b);
        return val[a] + val[b] - 2 * val[v];
    }
};

long long best[maxn];
int vis[maxn];

struct centroid {
    vector<vector<int>> edges;
    vector<bool> vis;
    vector<int> par, sz;

    int n;

    void init(int s) {
        n = s + 1;
        edges = vector<vector<int>>(n, vector<int>());
        vis = vector<bool>(n, 0);
        par = sz = vector<int>(n);
    }

    void edge(int a, int b) {
        edges[a].push_back(b);
        edges[b].push_back(a);
    }

    int find_size(int u, int p = -1) {
        if (vis[u])return 0;
        sz[u] = 1;
        for (auto x: edges[u]) {
            if (x == p)continue;
            sz[u] += find_size(x, u);
        }
        return sz[u];
    }

    int find_centroid(int u, int p, int n) {
        for (auto x:edges[u]) {
            if (x == p)continue;
            if (!vis[x] and sz[x] > n / 2)return find_centroid(x, u, n);
        }
        return u;
    }

    void init_centroid(int u = 1, int p = -1) {
        find_size(u);
        int c = find_centroid(u, -1, sz[u]);
        vis[c] = true;
        par[c] = p;

        for (auto x: edges[c]) {
            if (!vis[x])init_centroid(x, c);
        }
    }
};

int v[maxn];
centroid c;
lca_lift lca;

void Init(int N, int A[], int B[], int D[]) {
    c.init(N);
    lca.init(N);

    for (int i = 0; i < N - 1; i++) {
        c.edge(A[i] + 1, B[i] + 1);
        lca.edge(A[i] + 1, B[i] + 1, D[i]);
    }
    c.init_centroid();
    lca.init_lift();
}

int No = 1;

void update(int node) {
    int cur = node;
    while (cur != -1) {
        if (vis[cur] != No) {
            vis[cur] = No;
            best[cur] = lca.get_dist(cur, node);
        } else best[cur] = min(best[cur], lca.get_dist(cur, node));
        cur = c.par[cur];
    }
}

long long query(int node) {
    int cur = node;
    long long ans = LLONG_MAX;
    while (cur != -1) {
        if (vis[cur] == No) ans = min(ans, lca.get_dist(cur, node) + best[cur]);
        cur = c.par[cur];
    }
    return ans;
}

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

//void solve() {
//    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 j = 0; j < s; j++)cin >> X[j];
//        for (int j = 0; j < t; j++)cin >> Y[j];
//        cout << Query(s, X, t, Y) << endl;
//    }
//}

//int32_t main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(nullptr);
//
//    int t = 1;
////    cin >> t;
//
//    while (t--)
//        solve();
//    return 0;
//}

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