Submission #1316567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316567		a.pendov	Factories (JOI14_factories)	C++20	0 / 100	2305 ms	258196 KiB

factories

#include "factories.h"
#include "bits/stdc++.h"
using namespace std;
const long long MAXN=500000,inf=10000000000000000LL;
int pod[MAXN];
long long nearest[MAXN];
bool used[MAXN];
vector<pair<int,long long>> anc[MAXN];
vector<pair<int,int>> edg[MAXN];

inline long long min1(long long a,long long b)
{
    if(a>b)return b;
    return a;
}

int getSubSize(int start,int f)
{
    pod[start]=1;
    for(auto i:edg[start])
    {
        if(used[i.first]||f==i.first)continue;
        pod[start]+=getSubSize(i.first,start);
    }
    return pod[start];
}

int findCentr(int start,int f,int sz)
{
    for(auto i:edg[start])
    {
        if(used[i.first]||f==i.first)continue;
        if(pod[i.first]>sz/2)return findCentr(i.first,start,sz);
    }
    return start;
}

void findDist(int start,int f,int dist,int centrAnc)
{
    anc[start].push_back({centrAnc,dist});

    for(auto i:edg[start])
    {
        if(used[i.first]||f==i.first)continue;
        findDist(i.first,start,dist+i.second,centrAnc);
    }
}

void centrDec(int start)
{
    int centr=findCentr(start,-1,getSubSize(start,-1));
    used[centr]=1;
    anc[centr].push_back({centr,0});

    for(auto i:edg[centr])
    {
        if(used[i.first])continue;
        findDist(i.first,-1,i.second,centr);
    }

    for(auto i:edg[centr])
    {
        if(used[i.first])continue;
        centrDec(i.first);
    }
}

void addNode(int n)
{
    for(auto i:anc[n])
    {
        nearest[i.first]=min1(nearest[i.first],i.second);
    }
}

long long query(int n)
{
    long long ans=inf;
    for(auto i:anc[n])
    {
        ans=min1(nearest[i.first]+i.second,ans);
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[])
{
    for(int i=0;i<N-1;i++)
    {
        edg[A[i]].push_back({B[i],D[i]});
        edg[B[i]].push_back({A[i],D[i]});
    }

    centrDec(0);

    for(int i=0;i<N;i++)
    {
        nearest[i]=inf;
    }
}

long long Query(int S, int X[], int T, int Y[])
{
    long long ans=inf;

    for(int i=0;i<S;i++)
    {
        addNode(X[i]);
    }

    for(int i=0;i<T;i++)
    {
        ans=min1(ans,query(Y[i]));
    }

    for(int i=0;i<S;i++)
    {
        for(auto j:anc[X[i]])
        {
            nearest[j.first]=inf;
        }
    }

    return ans;
}

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