oj.uz

Submission #62064

# Submission time Handle Problem Language Result Execution time Memory
62064 2018-07-27T11:37:42 Z mohammedehab2002 Factories (JOI14_factories) C++11
0 / 100
 8000 ms 96080 KB 
#include "factories.h"
#include <string.h>
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int,int> > v[500005];
long long cum[500005];
bool del[500005];
int dep[500005],dp[20][500005],par[500005],sz[500005];
void dfs(int node,int p)
{
	for (auto u:v[node])
	{
		if (u.first!=p)
		{
			dep[u.first]=dep[node]+1;
			cum[u.first]=cum[node]+u.second;
			dp[0][u.first]=node;
			dfs(u.first,node);
		}
	}
}
int lca(int u,int v)
{
	if (dep[u]<dep[v])
	swap(u,v);
	int d=dep[u]-dep[v];
	for (int i=0;i<20;i++)
	{
		if (d&(1<<i))
		u=dp[i][u];
	}
	if (u==v)
	return u;
	for (int i=19;i>=0;i--)
	{
		if (dp[i][u]!=dp[i][v])
		{
			u=dp[i][u];
			v=dp[i][v];
		}
	}
	return dp[0][u];
}
long long dist(int a,int b)
{
	return cum[a]+cum[b]-2*cum[lca(a,b)];
}
void pre(int node,int p)
{
	sz[node]=1;
	for (auto u:v[node])
	{
		if (!del[u.first] && u.first!=p)
		{
			dfs(u.first,node);
			sz[node]+=sz[u.first];
		}
	}
}
int find(int node,int p,int n)
{
	for (auto u:v[node])
	{
		if (u.first!=p && !del[u.first] && sz[u.first]>n/2)
		return find(u.first,node,n);
	}
	return node;
}
void dfs2(int node,int p)
{
	pre(node,-1);
	int c=find(node,p,sz[node]);
	par[c]=p;
	del[c]=1;
	for (auto u:v[c])
	{
		if (!del[u.first])
		dfs2(u.first,c);
	}
}
long long ans[500005];
void update(int node,bool mem)
{
	int cur=node;
	while (cur!=-1)
	{
		if (mem)
		ans[cur]=(1LL<<60);
		else
		ans[cur]=min(ans[cur],dist(cur,node));
		cur=par[cur];
	}
}
long long query(int node)
{
	int cur=node;
	long long ret=(1LL<<60);
	while (cur!=-1)
	{
		ret=min(ret,dist(cur,node)+ans[cur]);
		cur=par[cur];
	}
	return ret;
}
void Init(int n,int a[],int b[],int d[])
{
	for (int i=0;i<n;i++)
	{
		v[a[i]].push_back({b[i],d[i]});
		v[b[i]].push_back({a[i],d[i]});
	}
	memset(dp,-1,sizeof(dp));
	dfs(0,-1);
	for (int i=1;i<20;i++)
	{
		for (int x=0;x<n;x++)
		{
			if (dp[i-1][x]!=-1)
			dp[i][x]=dp[i-1][dp[i-1][x]];
		}
	}
	dfs2(0,-1);
	for (int i=0;i<n;i++)
	update(i,1);
}
long long Query(int s,int x[],int t,int y[])
{
	for (int i=0;i<s;i++)
	update(x[i],0);
	long long ret=(1LL<<60);
	for (int i=0;i<t;i++)
	ret=min(ret,query(y[i]));
	for (int i=0;i<s;i++)
	update(x[i],1);
	return ret;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 51576 KB Output is correct
2 Correct 1801 ms 59960 KB Output is correct
3 Execution timed out 8064 ms 59960 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 59960 KB Output is correct
2 Execution timed out 8067 ms 96080 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 51576 KB Output is correct
2 Correct 1801 ms 59960 KB Output is correct
3 Execution timed out 8064 ms 59960 KB Time limit exceeded
4 Halted 0 ms 0 KB -