Submission #1243087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243087		Bui_Quoc_Cuong	Factories (JOI14_factories)	C++20	100 / 100	4288 ms	230748 KiB

factories

#include <bits/stdc++.h>
#include "factories.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);
    }
}

const int N = 5e5 + 5;
struct LowestCommonAncestor
{
    vector <int> nList, hList;
    int tin[N], tout[N], timeDFS;
    int rmq[4 * N][24];
    int h[N];
    ll sum[N];

    void dfs(int u,int p)
    {
        nList.pb(u); hList.pb(h[u]);
        tin[u] = ++ timeDFS;
        for(auto x :g[u])
        {
            int v= x[0], w = x[1];
            if(v==p) continue;
            h[v] = h[u] + 1;
            sum[v] = sum[u] + w;
            dfs(v,u);
            nList.pb(u); hList.pb(h[u]);
        }
        tout[u] = ++timeDFS;
    }

    int merge(int i,int j)
    {
        return (hList[i] < hList[j] ? i : j);
    }

    void init()
    {
        nList.pb(0); hList.pb(0);
        dfs(1,1);
        int m = nList.size()-1;
        FOR(i,1,m) rmq[i][0] = i;   
        for(int j =1;(1<<j)<=m;j++) FOR(i,1,m-(1<<j)+1)
        {
            rmq[i][j] =merge(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
        }
    }

    int lca(int u,int v)
    {
        if(tin[u] > tin[v]) swap(u, v);
        int k = __lg(tin[v]-tin[u]+1);
        return nList[merge(rmq[tin[u]][k], rmq[tin[v]-(1<<k)+1][k])]; 
    }

    ll dist(int u,int v)
    {
        return sum[u] + sum[v] - 2 * sum[lca(u, v)];
    }
} LCA;
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 = LCA.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 = LCA.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);
    LCA.init();
    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){\
        ok[X[i] + 1] = 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);
        ok[X[i] + 1] = 0;
    }
    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: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67