Submission #62341

#	Time	Username	Problem	Language	Result	Execution time	Memory
62341		mahmoudbadawy	Factories (JOI14_factories)	C++17	0 / 100	88 ms	94968 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define F first
#define S second
#pragma optimize("O3")
     
using namespace std;
 
const int N=500005;
 
long long dist[N],hi[N];
int dp[2*N][20];
vector<pair<int,int> > adj[N];
int n;
 
long long ss[N];
int par[N],sz[N],del[N];
long long dist2[N][20];
int lab[N],rlab[N];
int nc;
 
void dfs0(int node,int pa=0)
{
   	/*dp[node][0]=pa;
    for(int i=1;i<20;i++)
		dp[node][i]=dp[dp[node][i-1]][i-1];*/
    for(int i=0;i<adj[node].size();i++)
    {
		int x=adj[node][i].F,l=adj[node][i].S;
		if(x==pa) continue;
		dist[x]=dist[node]+l;
		hi[x]=hi[node]+1;
		dfs0(x,node);
    }
}


void dfs1(int node,int pa=0)
{
	sz[node]=1;
	nc++;
	for(int i=0;i<adj[node].size();i++)
	{
		int x=adj[node][i].F,l=adj[node][i].S;
		if(x==pa) continue;
		if(del[x]) continue;
		dfs1(x,node);
		sz[node]+=sz[x];
    }
}
 
int getCentroid(int node,int pa=0)
{
	for(int i=0;i<adj[node].size();i++)
	{
		int x=adj[node][i].F,l=adj[node][i].S;
		if(x==pa) continue;
		if(del[x]) continue;
		if(sz[x]>nc/2)
			return getCentroid(x,node);
	}
	return node;
}
 
void decompose(int node,int pa=-1,int dep=0)
{
	assert(dep<=21);
	nc=0;
	dfs1(node,node);
	int centroid=getCentroid(node,node);
	if(pa==-1) pa=centroid;
	par[centroid]=pa;
	del[centroid]=1;
	for(int i=0;i<adj[centroid].size();i++)
	{
		int x=adj[centroid][i].F;
		if(!del[x]) decompose(x,centroid,dep+1);
	}
}

// finding LCA

int eul[2*N];
int reul[N];
int log_2[2*N];
int eulc=1;

void geteul(int node,int pa=-1)
{
	eul[eulc++]=node;
	reul[node]=eulc-1;
	for(int i=0;i<adj[node].size();i++)
	{
		if(adj[node][i].F==pa) continue;
		geteul(adj[node][i].F,node);
		eul[eulc++]=node;
	}
}

void bfs()
{
	int cur_p=0;
	for(int i=0;i<2*N;i++)
	{
		if(i==(1<<cur_p))
			cur_p++;
		log_2[i]=cur_p-1;
	}
	queue<int> q;
	q.push(1);
	int x=1;
	while(q.size())
	{
		int cur=q.front();
		lab[cur]=x;
		rlab[x++]=cur;
		q.pop();
		for(int i=0;i<adj[cur].size();i++)
		{
			if(!lab[adj[cur][i].F]) q.push(adj[cur][i].F);
		}
	}
	geteul(1);
	for(int i=1;i<eulc;i++)
		dp[i][0]=eul[i];
	for(int i=1;i<20;i++)
	{
		for(int j=1;j<eulc;j++)
		{
			if(j+(1<<i)<eulc)
				dp[j][i]=min(dp[j][i-1],dp[j+(1<<(i-1))][i-1]);
		}
	}
}

int lca(int x,int y)
{
	/*if(hi[x]<hi[y]) swap(x,y);
	for(int i=19;i>=0;i--)
	{
		if(hi[x]-(1<<i)>=hi[y])
			x=dp[x][i];
	}
	if(x==y) return x;
	for(int i=19;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i]; y=dp[y][i];
		}
	}
	return dp[x][0];*/
	int s=reul[x],e=reul[y];
	if(s>e) swap(s,e);
	int len=e-s+1;
	len=log_2[len];
	return rlab[min(dp[s][len],dp[e-(1<<len)+1][len])];

}
 
long long getDist(int x,int y)
{
	return dist[x]+dist[y]-2*dist[lca(x,y)];
}
 
void add(int x)
{
	int lev=0;
	int z=x;
	while(true)
	{
		dist2[x][lev]=(dist2[x][lev]==-1?getDist(z,x):dist2[x][lev]);
		ss[z]=min(ss[z],dist2[x][lev]);
		lev++;
		assert(lev<=20);
		if(par[z]==z) break;
		z=par[z];
	}
}
 
void delet(int x)
{
	int z=x;
	int lev=0;
	while(true)
	{
		ss[z]=(1LL<<60);
		lev++;
		assert(lev<=20);
		if(par[z]==z) break;
		z=par[z];
	}
}
 
long long query(int x)
{
	long long ans=(1LL<<60);
	int z=x;
	int lev=0;
	while(true)
	{
		dist2[x][lev]=(dist2[x][lev]==-1?getDist(z,x):dist2[x][lev]);
		ans=min(ans,dist2[x][lev]+ss[z]);
		lev++;
		assert(lev<=20);
		if(par[z]==z) break;
		z=par[z];
	}
	return ans;
}
 
void Init(int N, int A[], int B[], int D[]) {
	
	n=N;
	for(int i=0;i<N-1;i++)
	{
		A[i]++; B[i]++;
		adj[A[i]].push_back({B[i],D[i]});
		adj[B[i]].push_back({A[i],D[i]});
	}
	//cerr << "DONE" << endl;
	dfs0(1);
	//cerr << "DONE" << endl;
	decompose(1);
	bfs();
	memset(dist2,-1,sizeof dist2);
	for(int i=1;i<=N;i++)
		ss[i]=(1LL<<60);
	//cerr << "DONE" << endl;
}
 
long long Query(int S, int X[], int T, int Y[]) {
	long long ans=(1LL<<60);
	for(int i=0;i<S;i++) X[i]++;
	for(int i=0;i<T;i++) Y[i]++;
	for(int i=0;i<S;i++) add(X[i]);
	for(int i=0;i<T;i++) ans=min(ans,query(Y[i]));
	for(int i=0;i<S;i++) delet(X[i]);
	return ans;
}

Compilation message (stderr)

factories.cpp:5:0: warning: ignoring #pragma optimize  [-Wunknown-pragmas]
 #pragma optimize("O3")
 
factories.cpp: In function 'void dfs0(int, int)':
factories.cpp:27:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<adj[node].size();i++)
                 ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void dfs1(int, int)':
factories.cpp:42:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp:44:24: warning: unused variable 'l' [-Wunused-variable]
   int x=adj[node][i].F,l=adj[node][i].S;
                        ^
factories.cpp: In function 'int getCentroid(int, int)':
factories.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp:56:24: warning: unused variable 'l' [-Wunused-variable]
   int x=adj[node][i].F,l=adj[node][i].S;
                        ^
factories.cpp: In function 'void decompose(int, int, int)':
factories.cpp:74:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[centroid].size();i++)
              ~^~~~~~~~~~~~~~~~~~~~~
factories.cpp: In function 'void geteul(int, int)':
factories.cpp:92:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp: In function 'void bfs()':
factories.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<adj[cur].size();i++)
               ~^~~~~~~~~~~~~~~~

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