Submission #1265201

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265201		canhnam357	Factories (JOI14_factories)	C++17	100 / 100	3612 ms	265872 KiB

factories

#include <bits/stdc++.h>
//#define int long long
#define MASK(i) (1LL << (i))
using namespace std;
const long long inf = 1e18;
const int N = 5e5 + 5;
// 1-indexed Centroid Decomposition
//int __lg(int n) { return log2(n) + 0.0001; } // Microsoft Visualstudio doesn't have __lg function, this help error not occurrence =))
vector<pair<int, int>> G[N];
int sz[N], par_centroid[N], h[N] = {}, id[N] = {}, par[N][19];
bool del[N] = {};
long long d[N][19], ans[N], dpar[N][19];
int timer;
int dfs(int u, int p) {
    sz[u] = 1;
    for (auto v : G[u]) if (v.first != p && !del[v.first]) {
        sz[u] += dfs(v.first, u);
    }
    return sz[u];
}
int centroid(int u, int p, int n) {
    for (auto v : G[u]) if (v.first != p && !del[v.first]) {
        if (sz[v.first] > n / 2) return centroid(v.first, u, n);
    }
    return u;
}
void build(int u, int p) {
    int n = dfs(u, p);
    int c = centroid(u, p, n);
    par_centroid[c] = p;
    del[c] = 1;
    for (auto v : G[c]) {
        if (!del[v.first])
            build(v.first, c);
    }
}
void first_dfs(int u, int p) {
    for (auto v : G[u]) if (v.first != p) {
        h[v.first] = h[u] + 1;
        par[v.first][0] = u;
        d[v.first][0] = v.second;
        first_dfs(v.first, u);
    }
}
long long get_dis(int u, int v)
{
    long long dis = 0;
    if (h[u] > h[v]) swap(u, v);
    int k = h[v] - h[u];
    int lg = (k == 0 ? -1 : __lg(k));
    for (int i = 0; i <= lg; i++) if (k & MASK(i))
    {
        dis += d[v][i];
        v = par[v][i];
    }
    if (v == u) return dis;
    lg = (h[v] == 0 ? -1 : __lg(h[v]));
    for (int i = lg; i >= 0; i--)
    {
        if (par[v][i] != par[u][i])
        {
            dis += d[v][i] + d[u][i];
            v = par[v][i];
            u = par[u][i];
        }
    }
    return dis + d[v][0] + d[u][0];
}
void modify(int u) {
    for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
    {
        if (id[v] == timer)
        {
            ans[v] = min(ans[v], dpar[u][level]);
        }
        else
        {
            id[v] = timer;
            ans[v] = dpar[u][level];
        }
    }
}
long long query(int u) {
    long long mn = inf;
    for (int v = u, level = 0; v != 0; v = par_centroid[v], level++)
    {
        if (id[v] == timer)
            mn = min(mn, ans[v] + dpar[u][level]);
    }
    return mn;
}
int n;
void solve()
{
    timer = 0;
    first_dfs(1, 0); // calculate h, par for lca
    // RMQ for lca
    {
        int lg = __lg(n);
        for (int i = 1; i <= lg; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                par[j][i] = par[par[j][i - 1]][i - 1];
                d[j][i] = d[j][i - 1] + d[par[j][i - 1]][i - 1];
            }
        }
    }
    build(1, 0);
    for (int i = 1; i <= n; i++)
    {
        for (int v = i, level = 0; v; v = par_centroid[v], level++)
        {
            dpar[i][level] = get_dis(i, v);
        }
    }
}
void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for (int i = 0; i < n - 1; i++)
    {
        A[i]++;
        B[i]++;
        int u = A[i], v = B[i], w = D[i];
        G[u].emplace_back(v, w);
        G[v].emplace_back(u, w);
    }
    solve();
}
long long Query(int S, int X[], int T, int Y[])
{
    timer++;
    int s = S, t = T;
    for (int i = 0; i < s; i++)
    {
        modify(X[i] + 1);
    }
    long long ans = inf;
    for (int i = 0; i < t; i++)
    {
        ans = min(ans, query(Y[i] + 1));
    }
    // cout << "ANSWER ";
    return ans;
}

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