Submission #563484

#	Time	Username	Problem	Language	Result	Execution time	Memory
563484		hibiki	Factories (JOI14_factories)	C++11	15 / 100	8096 ms	175968 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 cur,int st)
{
    mn[cur] = min(mn[cur],lca_query(st,cur));
    if(cen[cur] == cur) return ;
    cen_upd(cen[cur],st);
}

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

void Init(int N, int A[], int B[], int D[])
{
    n = N;
    for(int i = 0; i < n - 1; 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],X[i]);
    for(int i = 0; i < T; i++)
        ret = min(ret,cen_query(Y[i],Y[i]));
    return ret;
}

// int a[500005],b[500005],c[500005];
// int ps[500005],pt[500005];
// int main()
// {
//     int n,q;
//     scanf("%d %d",&n,&q);
//     for(int i = 0; i < n - 1; i++)
//     {
//         scanf("%d %d %d",&a[i],&b[i],&c[i]);
//     }
//     Init(n, a, b, c);
//     for(int i = 0; i < q; i++)
//     {
//         int s,t;
//         scanf("%d %d",&s,&t);
//         for(int j = 0; j < s; j++)
//             scanf("%d",&ps[j]);
//         for(int j = 0; j < t; j++)
//             scanf("%d",&pt[j]);
//         printf("%lld\n",Query(s, ps, t, pt));
//     }
//     return 0;
// }

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