Submission #1294702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1294702		harryleee	Factories (JOI14_factories)	C++20	0 / 100	8 ms	3144 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const int maxn = 5e5;
int n, q, a[maxn], b[maxn], h[maxn], x[1000000], y[1000000], d[maxn], child[maxn], par[maxn], st[maxn][20];
bool del[maxn];
long long ans[maxn], dis[maxn];
vector<pair<int, long long>> adj[maxn + 1];

void DFS(int u, int p){
    child[u] = 1;
    for (auto [v, w] : adj[u]) if (v != p && !del[v]){
        DFS(v, u);
        child[u] += child[v];
    }
    return;
}

int find_centroid(int u, int p, int num){
    for (auto [v, w] : adj[u]) if (v != p && !del[v]){
        if (child[v] > num / 2) return find_centroid(v, u, num);
    }
    return u;
}

void BFS(int u){
    queue<int> q;
    q.push(u);
    while(!q.empty()){
        int cur = q.front();
        q.pop();
        for (auto [v, w] : adj[u]) if (!del[v] && par[v] != u){
            par[v] = u;
            q.push(v);
        }
    }
    return;
}

void compute(int u){
    DFS(u, -1);
    int centroid = find_centroid(u, -1, child[u]);
    // cout << centroid << '\n';
    del[centroid] = true;
    BFS(centroid);

    for (auto [v, w] : adj[centroid]) if (!del[v])
        compute(v);
    return;
}

void DFS1(int u, int p){
    for (auto [v, w] : adj[u]) if (v != p){
        h[v] = h[u] + 1;
        dis[v] = dis[u] + w;
        st[v][0] = u;
        for (int i = 1; (1 << i) <= h[v] ; ++i){
            st[v][i] = st[st[v][i - 1]][i - 1];
        }

        DFS1(v, u);
    }
    return;
}

int lca(int u, int v){
    if (h[u] > h[v]) swap(u, v);
    int k = h[v] - h[u];
    for (int i = 0; i <= 19; ++i) if (k & (1 << i))
        v = st[v][i];
    if (u == v) return u;
    for (int i = 19; i >= 0; --i) if (st[u][i] != st[v][i]){
        u = st[u][i];
        v = st[v][i];
    }
    return st[u][0];
}

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

void Init(int N, int A[], int B[], int D[]){
    n = N;
    memset(del, false, sizeof(del));
    fill(par, par + maxn, -1);
    for (int i = 0; i < n; ++i){
        ans[i] = 1e18;
    }
    for (int i = 0; i < n - 1; ++i){
        adj[a[i]].push_back({b[i], d[i]});
        adj[b[i]].push_back({a[i], d[i]});
    }
    compute(0);
    // for (int i = 0; i < n; ++i) cout << par[i] << ' ';
    // cout << '\n';
    DFS1(0, -1);
    return;
}

long long Query(int S, int X[], int T, int Y[]){
    long long res = 1e18;
    for (int i = 0; i < T; ++i){
        int p = Y[i];
        while(p != -1){
            ans[p] = min(ans[p], length(Y[i], p));
            p = par[p];
        }
    };
    for (int i = 0; i < S; ++i){
        int p = X[i];
        while(p != -1){
            res = min(res, ans[p] + length(X[i], p));
            p = par[p];
        }
    }
    for (int i = 0; i < T; ++i){
        int p = Y[i];
        while(p != -1){
            ans[p] = 1e18;
            p = par[p];
        }
    };
    return res;
}

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