Submission #563472

#	Time	Username	Problem	Language	Result	Execution time	Memory
563472		hibiki	Factories (JOI14_factories)	C++11	0 / 100	8069 ms	131804 KiB

factories

#include"factories.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define f first
#define s second

// global
int n;
vector<pair<int,long long> > v[500005];

// lca
int deep[500005],spa[500005][20];
long long dist[500005][20];

void lca_dfs(int nw,int fa)
{
    for(auto go: v[nw])
    {
        if(go.f != fa)
        {
            deep[go.f] = deep[nw] + 1;
            spa[go.f][0] = nw;
            dist[go.f][0] = go.s;
            lca_dfs(go.f, nw);
        }
    }
}

void lca_init()
{
    memset(spa,-1,sizeof(spa));
    memset(dist,-1,sizeof(dist));
    deep[0] = 0;
    spa[0][0] = -1;
    dist[0][0] = -1;
    lca_dfs(0, -1);

    for(int j = 1; j < 20; j++)
    {
        for(int i = 0; i < n; i++)
        {
            if(spa[i][j - 1] == -1)
                continue;
            spa[i][j] = spa[spa[i][j - 1]][j - 1];
            dist[i][j] = dist[i][j - 1] + dist[spa[i][j - 1]][j - 1];
        }
    }
}

long long lca_query(int a,int b)
{
    long long ret = 0;
    if(deep[a] > deep[b]) swap(a,b);
    int diff = deep[b] - deep[a];
    for(int i = 0; i < 20; i++)
        if((1<<i)&diff)
        {
            ret += dist[b][i];
            b = spa[b][i];
        }
    if(a==b)
        return ret;
    for(int i = 19; i >= 0; i--)
    {
        if(spa[a][i] != spa[b][i])
        {
            ret += dist[a][i] + dist[b][i];
            a = spa[a][i];
            b = spa[b][i];
        }
    }
    return ret + dist[a][0] + dist[b][0];
}

// centroid
int cen[500005],sz[500005];
long long mn[500005];

int re_size(int nw,int fa)
{
    sz[nw] = 1;
    for(auto go: v[nw])
        if(go.f != fa && cen[go.f] == -1)
            sz[nw] += re_size(go.f,nw);
    return sz[nw];
}

int fi_cen(int nw,int fa,int sum)
{
    for(auto go: v[nw])
        if(go.f != fa && cen[go.f] == -1 && sz[go.f] > sum / 2)
            return fi_cen(go.f,nw,sum);
    return nw;
}

void centroid_decomp(int nw,int fa)
{
    int c = fi_cen(nw, -1, re_size(nw, -1));
    if(fa == -1) fa = c;
    cen[c] = fa;

    for(auto go: v[c])
        if(go.f != fa && cen[go.f] == -1)
            centroid_decomp(go.f, c);
}

void cen_upd(int nw)
{
    int cur = nw;
    while(cur != -1)
    {
        mn[cur] = min(mn[cur],lca_query(nw,cur));
        cur = cen[cur];
    }
}

long long cen_query(int nw)
{
    int cur = nw;
    long long ret = 1e18;
    while(cur != -1)
    {
        if(mn[cur] != 1e18)
            ret = min(ret,mn[cur] + lca_query(nw,cur));
        cur = cen[cur];
    }
    return ret;
}

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n; i++)
    {
        v[A[i]].pb({B[i],D[i]});
        v[B[i]].pb({A[i],D[i]});
    }

    memset(cen,-1,sizeof(cen));
    centroid_decomp(0, -1);

    lca_init();

    return ;
}

long long Query(int S, int X[], int T, int Y[])
{
    long long ret = 1e18;
    for(int i = 0; i < n; i++)
        mn[i] = 1e18;
    for(int i = 0; i < S; i++)
        cen_upd(X[i]);
    for(int i = 0; i < T; i++)
        ret = min(ret,cen_query(Y[i]));
    return ret;
}

// int main()
// {
//     return 0;
// }

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