Submission #1245680

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245680		nguyenhuythach	Factories (JOI14_factories)	C++20	100 / 100	5568 ms	190488 KiB

factories

#include "factories.h"
#include<bits/stdc++.h>
#define ll long long
#define L LLONG_MAX
#define fi first
#define se second
#define pii pair<int,ll>
#define pll pair<long long,long long>
#define sz(a) ((int)a.size())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define REP(i,k,j) for(int i=k;i>=j;i--)
#define FORD(i,a) for(auto i:a)
using namespace std;
const int nmax=5e5+1;
int n;
vector<pii> adj[nmax];
ll pfx[nmax],treesize[nmax],vst[nmax],nxt[nmax][21],par[nmax],depth[nmax];
ll mn[nmax];

void pre_dfs(int u,int v)
{
    treesize[u]=1;
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        pre_dfs(i.fi,u);
        treesize[u]+=treesize[i.fi];
    }
}

int centroid(int u,int v,int n)
{
    FORD(i,adj[u])
    {
        if(i.fi==v || vst[i.fi]) continue;
        if(treesize[i.fi]>n/2) return centroid(i.fi,u,n);
    }
    return u;
}

void dnc(int ct)
{
    pre_dfs(ct,0);
    vst[ct]=true;
    
    FORD(i,adj[ct])
    {
        if(vst[i.fi]) continue;
        int nxt_ct=centroid(i.fi,0,treesize[i.fi]);
        par[nxt_ct]=ct;
        dnc(nxt_ct);
    }
}

void dfs(int u,int v)
{
    FORD(i,adj[u])
    {
        if(i.fi==v) continue;
        pfx[i.fi]=pfx[u]+i.se;
        depth[i.fi]=depth[u]+1;
        nxt[i.fi][0]=u;
        dfs(i.fi,u);
    }
}

void buildjump()
{
    FOR(i,1,20) FOR(u,1,n) nxt[u][i]=-1;
    FOR(i,1,20) FOR(u,1,n) nxt[u][i]=nxt[nxt[u][i-1]][i-1];
}

ll lca(int u,int v)
{
    int preu=u,prev=v;
    if(depth[u]<depth[v]) swap(u,v);
    int dis=depth[u]-depth[v];
    REP(i,20,0) if(dis&(1<<i)) u=nxt[u][i];
    if(u==v) return pfx[preu]+pfx[prev]-pfx[u]*2;
    REP(i,20,0) if(nxt[u][i]!=-1 && nxt[v][i]!=-1 && nxt[u][i]!=nxt[v][i])
    {
        u=nxt[u][i];
        v=nxt[v][i];
    }
    return pfx[preu]+pfx[prev]-pfx[nxt[u][0]]*2;
}

void update(int x)
{
    mn[x]=0;
    int save=x;
    while(par[save])
    {
        mn[par[save]]=min(mn[par[save]],lca(x,par[save]));
        save=par[save];
    }
}

void reset(int x)
{
	mn[x]=L;
    int save=x;
    while(par[save])
    {
        mn[par[save]]=L;
        save=par[save];
    }
}

ll get(int x)
{
    ll ans=mn[x];
    int save=x;
    while(par[save])
    {
        if(mn[par[save]]!=L) ans=min(ans,mn[par[save]]+lca(x,par[save]));
        save=par[save];
    }
    return ans;
}

void Init(int N, int A[], int B[], int D[])
{
	n=N;
	FOR(i,0,n-2)
	{
		adj[A[i]+1].push_back({B[i]+1,D[i]});
		adj[B[i]+1].push_back({A[i]+1,D[i]});
	}
	
	//tim centroid dau tien
    pre_dfs(1,0);
    int ct=centroid(1,0,n);
    dnc(ct);
    
    dfs(1,0);
    buildjump();
    FOR(i,1,n) mn[i]=L;
}

long long Query(int S, int X[], int T, int Y[])
{
	FOR(i,0,S-1) update(X[i]+1);
	ll ans=L;
	FOR(i,0,T-1) ans=min(ans,get(Y[i]+1));
	FOR(i,0,S-1) reset(X[i]+1);
	return ans;
}

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