Submission #1175286

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175286		Haidara314	Factories (JOI14_factories)	C++20	0 / 100	380 ms	589824 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
using namespace std;
ll dis[500005];
bool vis[500005];
vector<pair<int,ll>>adj[500005];
vector<vector<pair<int,ll>>>cen(500005);
ll sz[500005];
void dfssz(int u,int p)
{
    if(vis[u])return;
    sz[u]=1;
    for(auto x:adj[u])
    {
        if(x.F==p)continue;
        dfssz(x.F,u);
        sz[u]+=sz[x.F];
    }
}
int getcen(int u,int s)
{
    //if(vis[u])return 0;
    int cent=u;
    for(auto x:adj[u])
    {
        if(sz[x.F]*2>s)
            cent=getcen(x.F,s);
    }
    return cent;
}
void dfscen(int u,int p,ll d,int t)
{
    if(vis[u])return;
    cen[u].push_back({t,d});
    for(auto x:adj[u])
    {
        if(x.F==p)continue;
        dfscen(x.F,u,x.S+d,t);
    }
}
void decompose(int u)
{
    dfssz(u,0);
    int cent=getcen(u,sz[u]);
    dfscen(cent,0,0,cent);
    vis[cent]=1;
    for(auto x:adj[cent])
    {
        if(vis[x.F])continue;
        decompose(x.F);
    }
}
void Init(int N, int A[], int B[], int D[]) {
    for(int i=0;i<N-1;i++)
    {
        adj[A[i]].push_back({B[i],D[i]});
        adj[B[i]].push_back({A[i],D[i]});
    }
    decompose(1);
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ans=1e18;
    for(int i=0;i<S;i++)
    {
        for(auto u:cen[X[i]])
        {
            dis[u.F]=1e18;
        }
    }
    for(int i=0;i<S;i++)
    {
        for(auto u:cen[X[i]])
        {
            dis[u.F]=min(dis[u.F],u.S);
        }
    }
    for(int i=0;i<T;i++)
    {
        for(auto u:cen[Y[i]])
        {
            ans=min(ans,dis[u.F]+u.S);
        }
    }
  return ans;
}

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