Submission #1245671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245671		nguyenhuythach	Factories (JOI14_factories)	C++20	0 / 100	16 ms	12356 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,int>
#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];
int pfx[nmax],treesize[nmax],vst[nmax],nxt[nmax][21],par[nmax],depth[nmax];
int 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];
}

int 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)
{
    int save=x;
    while(par[save])
    {
        mn[par[save]]=L;
        save=par[save];
    }
}

int get(int x)
{
    int 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);
	int ans=0;
	FOR(i,0,T-1) ans=min(ans,get(Y[i]+1));
	FOR(i,0,S-1) reset(X[i]+1);
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void reset(int)':
factories.cpp:104:23: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
  104 |         mn[par[save]]=L;
      |                       ^
factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:137:22: warning: overflow in conversion from 'long long int' to 'int' changes value from '9223372036854775807' to '-1' [-Woverflow]
  137 |     FOR(i,1,n) mn[i]=L;
      |                      ^

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