Submission #1175301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175301		Haidara314	Factories (JOI14_factories)	C++20	15 / 100	7638 ms	589824 KiB

factories

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#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<pair<int,ll>>cen[500005];
ll sz[500005];
void dfssz(int u,int p)
{
    //cout<<u<<" "<<p<<endl;
    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 p,int s)
{
    //if(vis[u])return 0;
    int cent=u;
    for(auto x:adj[u])
    {
        if(x.F==p||vis[x.F])continue;
        if(sz[x.F]*2>s)
            cent=getcen(x.F,u,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,int p)
{
    //cout<<u<<endl;
    dfssz(u,0);
    //cout<<u<<endl;
    int cent=getcen(u,p,sz[u]);
    //cout<<cent<<endl;
    dfscen(cent,0,0,cent);
    vis[cent]=1;
    for(auto x:adj[cent])
    {
        if(vis[x.F])continue;
        decompose(x.F,cent);
    }
}
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,0);
}
long long Query(int S, int X[], int T, int Y[]) {
    ll ans=1e18;
    for(int i=0;i<S;i++)
    {
        //cout<<X[i]<<" ";
        for(auto u:cen[++X[i]])
        {

            dis[u.F]=1e18;
        }
    }
    for(int i=0;i<T;i++)
    {
        for(auto u:cen[++Y[i]])
        {
            dis[u.F]=1e18;
        }
    }
    //cout<<endl;
    for(int i=0;i<S;i++)
    {
        for(auto u:cen[X[i]])
        {
            dis[u.F]=min(dis[u.F],u.S);
            //cout<<X[i]<<" "<<u.F<<" "<<u.S<<endl;
        }
    }
    for(int i=0;i<T;i++)
    {
        for(auto u:cen[Y[i]])
        {
            ans=min(ans,dis[u.F]+u.S);
            //cout<<Y[i]<<" "<<u.F<<" "<<dis[u.F]<<endl;
        }
    }
  return ans;
}

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