oj.uz

Submission #21064

# Submission time Handle Problem Language Result Execution time Memory
21064 2017-04-04T07:49:39 Z sbansalcs Factories (JOI14_factories) C++14
33 / 100
 6000 ms 254088 KB 
#include "factories.h"
#include <vector>
#include <iostream>
#include <assert.h>
using namespace std;
const int N = 500005;
typedef long long ll;
int dp[N][20],depth[N],subtree[N],vis[N],parent[N];
ll dist[N],XX[N][20];int PP[N][20];
int A[N];ll B[N];
vector<pair<int,int>> adj[N];
int logt[N];
int QUERY=0;
void dfs1(int v, int p, int dep, ll x)	{
	dp[v][0]=p;
	depth[v]=dep;
	dist[v]=x;
	for(int i=1;i<=logt[dep];i++)	dp[v][i]=dp[dp[v][i-1]][i-1];
	int c;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p)	continue;
		dfs1(c,v,dep+1,x+e.second);
	}
}

int find_centroid(int v, int p, int x)	{
	int c;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p || vis[c] || subtree[c]<=x)	continue;
		return find_centroid(c,v,x);
	}
	return v;
}

void dfs2(int v, int p)	{
	int c;
	subtree[v]=1;
	for(auto e:adj[v])	{
		c=e.first;
		if(c==p || vis[c] )	continue;
		dfs2(c,v);
		subtree[v]+=subtree[c];
	}
}

inline int lca(int a, int b)	{
	if(depth[a]>depth[b])	swap(a,b);
	for(int i=logt[depth[b]];i>=0;i--)	{
		if(depth[b]-(1<<i)>=depth[a])	b=dp[b][i];
	}
	if(a==b)	return a;
	for(int i=logt[depth[b]];i>=0;i--)	{
		if(dp[a][i]!=dp[b][i])	a=dp[a][i],b=dp[b][i];
	}
	return dp[a][0];
}

inline ll distance(int a, int b)	{
	return dist[a]+dist[b]-2*dist[lca(a,b)];
}

void process(int v, int p)	{

	dfs2(v,0);
	int u=find_centroid(v,0,subtree[v]/2);
	vis[u]=1;
	parent[u]=p;
	int p2=u;
	int i=0;
	PP[u][i]=p2;
	while(p2!=-1)	{
		XX[u][i]=distance(p2,u);
		p2=parent[p2];i++;
		PP[u][i]=p2;
	}
	// assert(i<=20);
	int c;
	for(auto e:adj[u])	{
		c=e.first;
		if(vis[c])	continue;
		process(c,u);
	}
}


void Init(int n, int A[], int B[], int D[]) {
	for(int i=0;i<=n-2;i++)	{
		adj[A[i]+1].push_back({B[i]+1,D[i]});
		adj[B[i]+1].push_back({A[i]+1,D[i]});
	}
	logt[0]=-1;
	for(int i=1;i<=n;i++)	{
		logt[i]=logt[i-1];
		if((i&-i)==i)	logt[i]++;
	}
	dfs1(1,0,0,0);
	process(1,-1);
}

long long Query(int S, int X[], int T, int Y[]) {
	QUERY++;
	int u,v;
	for(int i=0;i<S;i++)	{
		u=X[i]+1;
		for(int j=0;PP[u][j]!=-1;j++)	{
			v=PP[u][j];
			if(A[v]!=QUERY)	{
				A[v]=QUERY;B[v]=XX[u][j];
			}
			else if(B[v]>XX[u][j])	{
				B[v]=XX[u][j];
			}
		}
	}
	ll ans=1e17;
	for(int i=0;i<T;i++)	{
		u=Y[i]+1;
		for(int j=0;PP[u][j]!=-1;j++)	{
			v=PP[u][j];
			if(A[v]==QUERY)	{
				ans=min(XX[u][j]+B[v],ans);
			}

		}
	}

  	return ans;
}

Compilation message

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 211792 KB Output is correct
2 Correct 386 ms 212056 KB Output is correct
3 Correct 416 ms 212056 KB Output is correct
4 Correct 386 ms 212056 KB Output is correct
5 Correct 443 ms 212076 KB Output is correct
6 Correct 286 ms 212092 KB Output is correct
7 Correct 393 ms 212056 KB Output is correct
8 Correct 423 ms 212056 KB Output is correct
9 Correct 429 ms 212080 KB Output is correct
10 Correct 313 ms 212092 KB Output is correct
11 Correct 436 ms 212056 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 211792 KB Output is correct
2 Correct 2179 ms 230536 KB Output is correct
3 Correct 3879 ms 233524 KB Output is correct
4 Correct 1146 ms 231504 KB Output is correct
5 Correct 5909 ms 254088 KB Output is correct
6 Correct 4038 ms 233096 KB Output is correct
7 Correct 1139 ms 216032 KB Output is correct
8 Correct 716 ms 216024 KB Output is correct
9 Correct 1446 ms 218088 KB Output is correct
10 Correct 1169 ms 215940 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2526 ms 230536 KB Output is correct
2 Correct 2586 ms 230536 KB Output is correct
3 Correct 4429 ms 232540 KB Output is correct
4 Correct 4343 ms 233108 KB Output is correct
5 Correct 4566 ms 232976 KB Output is correct
6 Execution timed out 6000 ms 248316 KB Execution timed out
7 Halted 0 ms 0 KB -