Submission #1274266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1274266		nanaseyuzuki	Factories (JOI14_factories)	C++20	0 / 100	7 ms	1088 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
// Author: Kazuki_Will_Win_VOI_8703
#define fi first
#define se second
#define pii pair<int, int>
// #define int long long
#define all(a) a.begin(), a.end()
using namespace std;

const int mn = 5e5 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5;
const int inf = 1e9, base = 311;

int n, q, s, t, sz[mn], on[mn], par[mn], d[mn], dist[mn], h[mn], lowest[mn], st[mn], ft[mn], lg2[mn], timer = 0;
pii up[mn][21];
vector <pii> a[mn];

void txl(int u, int p){
    st[u] = ft[u] = ++ timer;
    up[timer][0] = {h[u], u};

    for(auto [v, w] : a[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        dist[v] = dist[u] + w;
        txl(v, u);

        ft[u] = ++ timer;
        up[timer][0] = {h[u], u};
    }
}

void build(){
    for(int k = 1; k <= 20; k++){
        for(int i = 1; i + (1 << k) - 1 <= timer; i++){
            up[i][k] = min(up[i][k - 1], up[i + (1 << (k - 1))][k - 1]);
        }
    }
    for(int i = 2; i <= timer; i++) lg2[i] = lg2[i / 2] + 1;
}

void pre_dfs(int u, int p){
    sz[u] = 1;
    for(auto [v, w] : a[u]){
        if(on[v] || v == p) continue;
        pre_dfs(v, u);
        sz[u] += sz[v];
    }
}

int get_centroid(int u, int p, int Reina){
    for(auto [v, w] : a[u]){
        if(on[v] || v == p) continue;
        if(2 * sz[v] >= Reina) return get_centroid(v, u, Reina);
    }
    return u;
}

void dfs(int u, int p){
    pre_dfs(u, 0);
    u = get_centroid(u, 0, sz[u]);
    par[u] = p, on[u] = 1;
    d[u] = d[p] + 1;
    for(auto [v, w] : a[u]){
        if(on[v]) continue;
        dfs(v, u);
    }
}

int lca(int u, int v){
    if(st[u] > st[v]) swap(u, v);
    u = st[u], v = ft[v];
    int i = lg2[v - u + 1];
    return min(up[u][i], up[v - (1 << i) + 1][i]).se;
}

int kc(int u, int v){
    int p = lca(u, v);
    return dist[u] + dist[v] - 2 * dist[p];
}

void update(int u){
    int p = u;
    while(p){
        lowest[p] = min(lowest[p], kc(u, p));
        p = par[p];
    }
}

int get(int u){
    int p = u, res = inf;
    while(p){
        res = min(res, kc(u, p) + lowest[p]);
        p = par[p];
    }
    return res;
}

void rollback(int u){
    int p = u;
    while(p){
        lowest[p] = inf, p = par[p];
    }
}

void Init(int N, int A[], int B[], int D[]) {
    n = N;
    for(int i = 0; i < n - 1; i++){
        int u = A[i], v = B[i], w = D[i];
        ++ u, ++ v;
        a[u].push_back({v, w});
        a[v].push_back({u, w});
    }
    txl(1, 0);
    build();
    dfs(1, 0);
    for(int i = 1; i <= n; i++) lowest[i] = inf;
}

long long Query(int S, int X[], int T, int Y[]) {
    for(int i = 0; i < S; i++){
        ++ X[i];
        int x = X[i], update(x);
    }
    int res = inf;
    for(int i = 0; i < T; i++){
        ++ Y[i];
        res = min(res, get(Y[i]));
    }
    for(int i = 0; i < S; i++) rollback(X[i]);
    return res;
}

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