Submission #1126387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126387		whoknow	Factories (JOI14_factories)	C++20	0 / 100	16 ms	12816 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define MAXN  500005
#define ii pair<int,int>
#define bit(i,j) ((i>>j)&1)
#define sz(i) (int)i.size()
#define endl '\n'
using namespace std;
const ll INF = 1e18;
int n, ntest;
vector<ii>g[MAXN];
int timedfs, Q;
ll best[MAXN], dist[MAXN];
bool A[MAXN], B[MAXN], del[MAXN];
int timed[MAXN], range[MAXN], sz[MAXN], par[MAXN], h[MAXN];
int f[2 * MAXN][20];
int minimize(int x, int y)
{
    if(h[x] < h[y])
        return x;
    return y;
}
int log2(int x)
{
    return 31 - __builtin_clz(x);
}
void build(int u, int p)
{
    h[u] = h[p] + 1;
    f[++timedfs][0] = u;
    range[u] = timedfs;
    for(ii v : g[u])
    {
        if(v.F == p)
            continue;
        dist[v.F] = dist[u] + v.S;
        build(v.F, u);
        f[++timedfs][0] = u;
    }
}
void RMQ()
{
    for(int j = 1; j <= log2(timedfs); j++)
        for(int i = 1; i <= timedfs - (1 << j) + 1; i++)
            f[i][j] = minimize(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
}
int lca(int u, int v)
{
    int l = range[u], r = range[v];
    if(l > r)
        swap(l, r);
    int k = log2(r - l + 1);
    return minimize(f[l][k], f[r - (1 << k) + 1][k]);
}
int get_size(int u, int p)
{
    int cnt = 1;
    for(ii v : g[u])
        if(v.F != p && !del[v.F])
            cnt += get_size(v.F, u);
    return sz[u] = cnt;
}
int get_centroid(int u, int p, int size)
{
    for(ii v : g[u])
        if(v.F != p && !del[v.F] && sz[v.F] > size / 2)
            return get_centroid(v.F, u, size);
    return u;
}
void dfs(int u, int p)
{
    u = get_centroid(u, 0, get_size(u, 0));
    del[u] = 1;
    par[u] = p;
    for(ii v : g[u])
        if(!del[v.F])
            dfs(v.F, u);
}
void update(int u)
{
    int v = u;
    while(u != 0)
    {
        if(timed[u] != Q)
            best[u] = dist[u] + dist[v] - 2LL * dist[lca(v, u)], timed[u] = Q;
        else
            best[u] = min(best[u], dist[u] + dist[v] - 2LL * dist[lca(v, u)]);
        u = par[u];
    }
}
ll get(int u)
{
    int v = u;
    ll ans = INF;
    while(u != 0)
    {
        if(timed[u] == Q)
            ans = min(ans, dist[u] + dist[v] - 2LL * dist[lca(u, v)]+best[u]);
        u = par[u];
    }
    return ans;
}
void Init(int N,int A[],int B[],int D[])
{
    for(int i=1;i<N;i++)
    {
        A[i]++,B[i]++;
        g[A[i]].push_back({B[i],D[i]});
        g[B[i]].push_back({A[i],D[i]});
    }
    build(1, 0);
    RMQ();
    dfs(1, 0);
}
ll Query(int S,int X[],int T,int Y[])
{
    Q++;
    ll res=INF;
    for(int i=1;i<=S;i++)
    {
        X[i]++;
        update(X[i]);
    }
    for(int i=1;i<=T;i++)
    {
        Y[i]++;
        res=min(res,get(Y[i]));
    }
    return res;
}

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