Submission #1243079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243079		Bui_Quoc_Cuong	Factories (JOI14_factories)	C++20	0 / 100	28 ms	39748 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i, a, b) for(int i = a, _b = b; i <= (_b); i++)
#define FORD(i, a, b) for(int i = a, _b = b; i >= (_b); i--)
#define ALL(A) A.begin(), A.end()
#define fi first
#define se second
#define pb push_back
const int maxn = 5e5 + 5;

int n, q;
vector <array <int, 2>> g[maxn];

int sz[maxn], is_centroid[maxn];
int par[maxn];
int P[maxn][20], h[maxn];
long long sum[maxn];

void dfs(int u, int p){
    sz[u] = 1;
    for(auto it : g[u]){
        int v = it[0];
        if(v == p || is_centroid[v]) continue;
        dfs(v, u);
        sz[u]+= sz[v];
    }
}

int findCentroid(int u, int p, int big){
    for(auto it : g[u]){
        int v = it[0];
        if(v == p || is_centroid[v]) continue;
        if(sz[v] > big / 2) return findCentroid(v, u, big);
    }
    return u;
}

void buildCentroid(int u, int preCentroid){
    dfs(u, - 1);
    int centroid = findCentroid(u, - 1, sz[u]);
    is_centroid[centroid] = true;
    par[centroid] = preCentroid;
    for(auto it : g[centroid]){
        int v = it[0];
        if(is_centroid[v]) continue;
        buildCentroid(v, centroid);
    }
}

void dfs_lca(int u){
    for(auto it : g[u]){
        int v = it[0], w = it[1];
        if(v == P[u][0]) continue;
        P[v][0] = u;
        h[v] = h[u] + 1;
        sum[v] = sum[u] + w;
        for(int j = 1; (1 << j) <= n; j++) P[v][j] = P[P[v][j - 1]][j - 1];
        dfs_lca(v);
    }
}

int LCA(int u, int v){
    if(h[u] < h[v]) swap(u, v);
    int z = __lg(h[u]);
    FORD(s, z, 0) if(h[u] - h[v] >= (1 << s)) u = P[u][s];
    if(u == v) return u;
    FORD(s, z, 0) if(P[u][s] != P[v][s]) u = P[u][s], v = P[v][s];
    return P[u][0];
}

long long dist(int u, int v){
    return sum[u] + sum[v] - 2 * sum[LCA(u, v)];
}

set <pair <long long, int>> best[maxn];
long long bestMinSon[maxn];

void update(int u){
    int son = u, v = par[u];
    for(; v; v = par[v]){
        long long cost = dist(u, v);
        if(bestMinSon[son] > cost){
            best[v].erase({bestMinSon[son], son});
            bestMinSon[son] = cost;
            best[v].insert({bestMinSon[son], son});
        }
        son = v;
    }
}

bool ok[maxn];

void del(int u){
    int son = u, v = par[u];
    for(; v; v = par[v]){
        best[v].clear();
        bestMinSon[son] = 1e18;
        son = v;
    }
}

long long get(int u){
    long long res = 1e18;
    if(best[u].size()){
        res = min(res, best[u].begin() -> first);
    }       
    int son = u, v = par[u];
    for(; v; v = par[v]){
        long long cost = dist(u, v);
        if(ok[v]){
            res = min(res, cost);
        }
        if(best[v].size()){
            if(best[v].begin() -> second == son){
                auto it = best[v].begin();
                it++;
                if(it != best[v].end()){
                    res = min(res, cost + it -> first);
                }
            } else{
                res = min(res, cost + best[v].begin() -> first);
            }
        }
    }
    return res;
}

void process(void){
    buildCentroid(1, 0);
    dfs_lca(1);
    memset(bestMinSon, 0x3f, sizeof bestMinSon);    
    // while(q--){
    //     int numS, numT; cin >> numS >> numT;
    //     vector <int> vers;
    //     FOR(i, 1, numS){
    //         int u; cin >> u; u++;
    //         vers.push_back(u);
    //         ok[u] = 1;
    //         update(u);
    //     }
    //     long long ans = 1e18;
    //     FOR(i, 1, numT){
    //         int u; cin >> u; u++;
    //         ans = min(ans, get(u));
    //     }
    //     cout << ans << "\n";
    //     for(int &u : vers){
    //         ok[u] = 0;
    //         del(u);
    //     }
    // }
}

void Init(int N, int A[], int B[], int D[]){
    n = N;
    FOR(i, 1, n - 1){
        int u = A[i - 1], v = B[i - 1], w = D[i - 1];
        u++; v++;
        g[u].push_back({v, w}); g[v].push_back({u, w});
    }
    process();
}

long long Query(int S, int X[], int T, int Y[]){
    FOR(i, 0, S - 1){
        update(X[i] + 1);
    }
    long long res = 1e18;
    FOR(i, 0, T - 1){
        res = min(res, get(Y[i] + 1));
    }
    FOR(i, 0, S - 1){
        del(X[i] + 1);
    }
    return res;
}

// signed main(void){
//     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//     #define taskname "kieuoanh"
//     if(fopen(taskname".inp", "r")){
//         freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout);
//     }
//     cin >> n >> q;
//     FOR(i, 1, n - 1){
//         int u, v, w; cin >> u >> v >> w;
//         ++u; ++v;
//         g[u].push_back({v, w}); g[v].push_back({u, w});
//     }

//     process();

//     return 0;
// }

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