oj.uz

Submission #61990

# Submission time Handle Problem Language Result Execution time Memory
61990 2018-07-27T08:08:14 Z mahmoudbadawy Factories (JOI14_factories) C++17
15 / 100
 8000 ms 187716 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)
{
	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);
	}
}

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 lev=0;
	int z=x;
	while(true)
	{
		ss[z].insert({getDist(z,x),x});
		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].clear();
		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)
	{
		if(ss[z].size()){
			pair<long long,int> pp=(*ss[z].begin());
			ans=min(ans,getDist(x,pp.S));
		}
		lev++;
		assert(lev<=20);
		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]});
	}
	//cerr << "DONE" << endl;
	dfs0(1);
	//cerr << "DONE" << endl;
	decompose(1);
	//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

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:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[centroid].size();i++)
              ~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 35964 KB Output is correct
2 Correct 3335 ms 45140 KB Output is correct
3 Correct 4566 ms 45140 KB Output is correct
4 Correct 7315 ms 47336 KB Output is correct
5 Correct 7157 ms 55560 KB Output is correct
6 Correct 845 ms 63944 KB Output is correct
7 Correct 4706 ms 73496 KB Output is correct
8 Correct 4954 ms 82952 KB Output is correct
9 Correct 7779 ms 93660 KB Output is correct
10 Correct 1026 ms 101808 KB Output is correct
11 Correct 4984 ms 111444 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 111444 KB Output is correct
2 Correct 5492 ms 186796 KB Output is correct
3 Execution timed out 8061 ms 187716 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 35964 KB Output is correct
2 Correct 3335 ms 45140 KB Output is correct
3 Correct 4566 ms 45140 KB Output is correct
4 Correct 7315 ms 47336 KB Output is correct
5 Correct 7157 ms 55560 KB Output is correct
6 Correct 845 ms 63944 KB Output is correct
7 Correct 4706 ms 73496 KB Output is correct
8 Correct 4954 ms 82952 KB Output is correct
9 Correct 7779 ms 93660 KB Output is correct
10 Correct 1026 ms 101808 KB Output is correct
11 Correct 4984 ms 111444 KB Output is correct
12 Correct 39 ms 111444 KB Output is correct
13 Correct 5492 ms 186796 KB Output is correct
14 Execution timed out 8061 ms 187716 KB Time limit exceeded
15 Halted 0 ms 0 KB -