제출 #1281851

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281851		quan606303	공장들 (JOI14_factories)	C++20	100 / 100	2860 ms	344236 KiB

factories

/*
 * @Author: RMQuan 
 * @Date: 2025-10-22 12:01:01 
 * @Last Modified by: RMQuan
 * @Last Modified time: 2025-10-22 12:49:49
 */
/*idea : 



*/
#include <bits/stdc++.h>
bool M1;
#define ll long long
#define INTMAX INT_MAX
#define INTMIN INT_MIN
#define LONGMAX LLONG_MAX
#define LONGMIN LLONG_MIN
#define fi first
#define se second
#define memfull(a,b) memset(a,b,sizeof(a));
#define endl '\n'
#define TASK "TEST"
#define file() if (fopen(TASK".inp","r")){freopen(TASK".inp","r",stdin); freopen(TASK".out","w",stdout);}
using namespace std;
const ll MOD=1e9+7;
const ll maxn=5e5+7;
const ll LOG=20;
const ll inf=1e18;
vector<pair<ll,ll> > adj[maxn];
ll n,q,rmq[2*maxn][LOG+1],pos[maxn],id_rmq=0,h[maxn],depth[maxn],sz[maxn];
bool is_deleted[maxn];
ll mn_dis[maxn];
vector<pair<ll,ll> > centroid_root[maxn];
void dfs(ll u,ll p)
{
    pos[u]=++id_rmq;
    rmq[id_rmq][0]=u;
    for (auto v:adj[u])
    {
        if (v.fi==p)continue;
        h[v.fi]=h[u]+1;
        depth[v.fi]=h[u]+v.se;
        dfs(v.fi,u);
        rmq[++id_rmq][0]=u;
    }
}
ll get_min(ll u,ll v)
{
    return (h[u]<h[v]?u:v);
}
ll lca(ll u,ll v)
{
    ll L=pos[u];
    ll R=pos[v];
    if (L>R)swap(L,R);
    ll k=__lg(R-L+1);
    return get_min(rmq[L][k],rmq[R-(1<<k)+1][k]);
}
void prepare()
{
    for (ll j=1;j<=LOG;j++)
    {
        for (ll i=1;i<=id_rmq;i++)rmq[i][j]=get_min(rmq[i][j-1],rmq[i+(1<<(j-1))][j-1]);
    }
}
void pre_dfs(ll u,ll p)
{
    sz[u]=1;
    for (auto v:adj[u])
    {
        if (v.fi==p||is_deleted[v.fi])continue;
        pre_dfs(v.fi,u);
        sz[u]+=sz[v.fi];
    }
}
ll find_centroid(ll u,ll p,ll N)
{
    for (auto v:adj[u])
    {
        if (v.fi==p||is_deleted[v.fi])continue;
        if (sz[v.fi]>=N)return find_centroid(v.fi,u,N);
    }
    return u;
}
void cal(ll u,ll p,ll w,ll root)
{
    centroid_root[u].push_back({root,w});
    for (auto v:adj[u])
    {
        if (v.fi==p||is_deleted[v.fi])continue;
        cal(v.fi,u,w+v.se,root);
    }
}
void decomposition(ll u)
{
    pre_dfs(u,0);
    ll N=sz[u];
    ll root=find_centroid(u,0,N/2);
    is_deleted[root]=true;
    centroid_root[root].push_back({root,0});
    for (auto v:adj[root])
    {
        if (!is_deleted[v.fi])cal(v.fi,root,v.se,root);
    }
    for (auto v:adj[root])if (!is_deleted[v.fi])decomposition(v.fi);
}
void Init(int N, int A[], int B[], int D[])
{
    n=N;
    for (int i=0;i<=N-2;i++)
    {
        int x=A[i]+1;
        int y=B[i]+1;
        ll w=D[i];
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    decomposition(1);
    for (int i=1;i<=n;i++)mn_dis[i]=inf;
}
long long Query(int S, int X[], int T, int Y[])
{
    vector<int> s;
    vector<int> t;
    for (int i=0;i<S;i++)s.push_back(X[i]+1);
    for (int i=0;i<T;i++)t.push_back(Y[i]+1);
    ll ans=inf;
    for (auto i:s)
    {
        for (auto j:centroid_root[i])mn_dis[j.fi]=min(mn_dis[j.fi],j.se);
    }
    for (auto i:t)
    {
        for (auto j:centroid_root[i])ans=min(ans,mn_dis[j.fi]+j.se);
    }
    for (auto i:s)
    {
        for (auto j:centroid_root[i])mn_dis[j.fi]=inf;
    }
    return ans;
}

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