oj.uz

답안 #21060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
21060 2017-04-04T07:36:36 Z sbansalcs 공장들 (JOI14_factories) C++14
15 / 100
 6000 ms 272580 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],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];
	}
}

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

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;
	}
	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];
			assert(XX[u][j]==distance(u,v));
			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];
						assert(XX[u][j]==distance(u,v));

			if(A[v]==QUERY)	{
				// A[v]=QUERY;B[v]=X[u][j];
				ans=min(XX[u][j]+B[v],ans);
			}

		}
	}

  	return ans;
}

Compilation message

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 250852 KB Output is correct
2 Correct 749 ms 251116 KB Output is correct
3 Correct 1819 ms 251116 KB Output is correct
4 Correct 1759 ms 251116 KB Output is correct
5 Correct 2659 ms 251136 KB Output is correct
6 Correct 336 ms 251152 KB Output is correct
7 Correct 1856 ms 251116 KB Output is correct
8 Correct 1886 ms 251116 KB Output is correct
9 Correct 2549 ms 251132 KB Output is correct
10 Correct 339 ms 251152 KB Output is correct
11 Correct 1896 ms 251116 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 250852 KB Output is correct
2 Correct 3193 ms 269596 KB Output is correct
3 Execution timed out 6000 ms 272580 KB Execution timed out
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4359 ms 269596 KB Output is correct
2 Correct 4416 ms 269596 KB Output is correct
3 Execution timed out 6000 ms 271600 KB Execution timed out
4 Halted 0 ms 0 KB -