oj.uz

Submission #61986

# Submission time Handle Problem Language Result Execution time Memory
61986 2018-07-27T07:42:25 Z mahmoudbadawy Factories (JOI14_factories) C++11
0 / 100
 8000 ms 120296 KB 
#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[N];

set< pair<long long,int> > ss[N];
int par[N],sz[N],del[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)
{
	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);
	}
}

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 add(int x)
{
	int z=x;
	while(true)
	{
		ss[z].insert({getDist(z,x),x});
		if(par[z]==z) break;
		z=par[z];
	}
}

void delet(int x)
{
	int z=x;
	while(true)
	{
		ss[z].erase({getDist(z,x),x});
		if(par[z]==z) break;
		z=par[z];
	}
}

long long query(int x)
{
	long long ans=(1LL<<60);
	int z=x;
	while(true)
	{
		if(ss[z].size()){
			pair<long long,int> pp=(*ss[z].begin());
			ans=min(ans,getDist(x,pp.S));
		}
		if(par[z]==z) break;
		z=par[z];
	}
	return ans;
}

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]});
	}
	dfs0(1);
	decompose(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++)
		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

factories.cpp: In function 'void dfs0(int, int)':
factories.cpp:23: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 dfs1(int, int)':
factories.cpp:37:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp:39: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:49:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[node].size();i++)
              ~^~~~~~~~~~~~~~~~~
factories.cpp:51: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)':
factories.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[centroid].size();i++)
              ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 36088 KB Output is correct
2 Correct 5404 ms 45320 KB Output is correct
3 Execution timed out 8007 ms 46680 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 46680 KB Output is correct
2 Correct 6822 ms 120296 KB Output is correct
3 Execution timed out 8063 ms 120296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 36088 KB Output is correct
2 Correct 5404 ms 45320 KB Output is correct
3 Execution timed out 8007 ms 46680 KB Time limit exceeded
4 Halted 0 ms 0 KB -