Submission #563690

#	Time	Username	Problem	Language	Result	Execution time	Memory
563690		hibiki	Factories (JOI14_factories)	C++11	15 / 100	8053 ms	155616 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];

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

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 get_dist(int nw,int fa,int lv)
{
    for(auto go: v[nw])
    {
        if(go.f != fa && cen[go.f] == -1)
        {
            dist[go.f][lv] = dist[nw][lv] + go.s;
            get_dist(go.f,nw,lv);
        }
    }
}

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

    get_dist(c, -1, deep[c]);
    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 != -2)
    {
        mn[cur] = min(mn[cur],dist[nw][deep[cur]]);
        cur = cen[cur];
    }
}

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

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(dist,0,sizeof(dist));
    memset(cen,-1,sizeof(cen));
    centroid_decomp(0, -2);

    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 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