Submission #1051533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051533		phong	Factories (JOI14_factories)	C++17	100 / 100	4005 ms	169404 KiB

factories

//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include "factories.h"

#define ll long long
const int nmax = 5e5 + 5, N = 1e6;
const ll oo = 1e18 + 5, base = 311;
const int lg = 18, tx = 26;
const ll mod = 998244353;
#define pii pair<ll, ll>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, q;
vector<pii> adj[nmax];
int h[nmax], up[nmax][lg + 1];
ll d[nmax];

void dfs_1(int u, int p){
    for(auto [w, v] : adj[u]){
        if(v == p) continue;
        h[v] = h[u] + 1;
        up[v][0] = u;
        d[v] = d[u] + w;
        for(int j = 1; j <= lg; ++j) up[v][j] = up[up[v][j - 1]][j - 1];
        dfs_1(v, u);
    }
}
int lca(int u, int v){
    if(h[u] != h[v]){
        if(h[u] < h[v]) swap(u, v);
        int k = h[u] - h[v];
        for(int j = 0; j <= __lg(k); ++j){
            if(k >> j & 1) u = up[u][j];
        }
    }
    if(u == v) return u;
    for(int j = __lg(h[u]); j >=0;--j){
        if(up[u][j] != up[v][j]){
            u = up[u][j];
            v = up[v][j];
        }
    }
    return up[u][0];
}
ll dist(int u, int v){
    return d[u] + d[v] - 2 * d[lca(u, v)];
}
bool vis[nmax];
int sz[nmax], par[nmax];

void dfs_2(int u, int p){
    sz[u] = 1;
    for(auto [w, v] : adj[u]){
        if(v == p || vis[v]) continue;
        dfs_2(v, u);
        sz[u] += sz[v];
    }
}
int cntw  = 0;
int Find(int u, int p){
    for(auto [w,v] : adj[u]){
        if(v == p || vis[v]) continue;
        if(sz[v] > cntw / 2) return Find(v, u);
    }
    return u;
}
int centroid(int u){
    dfs_2(u, -1); cntw = sz[u];
    int root = Find(u, -1);
    vis[root] = 1;
    for(auto [w, v] : adj[root]){
        if(vis[v]) continue;
        int x = centroid(v);
        par[x] = root;
    }
    return root;
}
vector<int> rev;
ll dp[nmax];
void update(int u){
    int x = u;
    while(u > 0){
        dp[u] = min(dp[u], dist(u, x));
        rev.push_back(u);
        u = par[u];
    }
}
ll get(int u){
    int x = u;
    ll res = oo;
    while(u > 0){
        res = min(res, dp[u] + dist(u, x));
        u = par[u];
    }
    return res;
}
int X[nmax], Y[nmax], S, T;
void Init(int n, int A[], int B[], int D[]){
    for(int i = 0; i < n - 1; ++i){
        int u, v, w;
        u = A[i], v = B[i], w = D[i];
        ++u, ++v;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }
    dfs_1(1, -1);
    centroid(1);
    memset(dp, 0x3f, sizeof dp);
}
ll Query(int S, int X[], int T, int Y[]){
    for(int i = 0; i < S; ++i) ++X[i];
    for(int i = 0; i < T; ++i) ++Y[i];
    for(int i = 0; i < S; ++i) update(X[i]);
    ll ans = oo;
    for(int i = 0; i < T; ++i){
        ans = min(ans,get(Y[i]));
    }
    for(auto p : rev)dp[p] = oo;
    rev.clear();
    return ans;
}

/*

*/

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