Submission #61972

#	Time	Username	Problem	Language	Result	Execution time	Memory
61972		mahmoudbadawy	Factories (JOI14_factories)	C++17	0 / 100	8029 ms	111800 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int N=500005;

long long dist[N],hi[N];
int dp[N][20];
vector<pair<int,int> > adj[100005];

void dfs(int node,int pa=-1)
{
	if(pa!=-1)
	{
		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;
		dfs(x,node);
	}
}

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];
}

long long getDist(int x,int y)
{
	return dist[x]+dist[y]-2*dist[lca(x,y)];
}

void Init(int N, int A[], int B[], int D[]) {
	
	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]});
	}
	dfs(1);
}

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++)
		for(int j=0;j<T;j++)
			ans=min(ans,getDist(X[i],Y[j]));
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~

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