oj.uz

Submission #416509

# Submission time Handle Problem Language Result Execution time Memory
416509 2021-06-02T14:06:17 Z T0p_ Factories (JOI14_factories) C++14
0 / 100
 8000 ms 12492 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;
 
#define N 500500
#define pb push_back
 
struct GRAPH
{
	int node;
	long long weight;
};
 
int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N], dp[20][N];
bool visit[N];
vector<GRAPH> g[N];
 
int get_sz(int u, int p)
{
	sz[u] = 1;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		sz[u] += get_sz(x.node, u);
	}
	return sz[u];
}
 
int get_centroid(int u, int p, int n)
{
	bool ch = (n - sz[u] <= n/2) ? true : false;
	int uu = 0;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		if(sz[x.node] > sz[uu])
		{
			ch = false;
			uu = x.node;
		}
	}
	return (ch) ? u : get_centroid(uu, u, n);
}
 
int build(int u, int p)
{
	int c = get_centroid(u, p, get_sz(u, p));
	visit[c] = true;
	for(auto x : g[c])
	{
		if(visit[x.node]) continue ;
		pa[build(x.node, c)] = c;
	}
	return c;
}
 
void dfs(int u, int l)
{
	lv[u] = l;
	for(auto x : g[u])
	{
		if(lv[x.node]) continue ;
		jmp_node[0][x.node] = u;
		jmp_dis[0][x.node] = x.weight;
		dfs(x.node, l+1);
	}
}
 
long long get_dis(int u, int v)
{
	long long ret = 0;
	if(lv[u] < lv[v]) swap(u, v);
	for(int i=19 ; i>=0 ; i--)
		if(lv[jmp_node[i][u]] >= lv[v])
		{
			ret += jmp_dis[i][u];
			u = jmp_node[i][u];
		}
	if(u == v) return ret;
	for(int i=19 ; i>=0 ; i--)
		if(jmp_node[i][u] != jmp_node[i][v])
		{
			ret += jmp_dis[i][u] + jmp_dis[i][v];
			u = jmp_node[i][u], v = jmp_node[i][v];
		}
	return ret + jmp_dis[0][u] + jmp_dis[0][v];
}
 
void Init(int n, int u[], int v[], int w[])
{
	for(int i=0 ; i<n-1 ; i++)
	{
		g[u[i]+1].pb({v[i]+1, w[i]});
		g[v[i]+1].pb({u[i]+1, w[i]});
	}
	dfs(1, 1);
	build(1, 0);
	for(int i=1 ; i<=n ; i++)
	{
		visit[i] = false;
		dis[i] = 1e15;
	}
	for(int i=1 ; i<20 ; i++)
		for(int j=1 ; j<=n ; j++)
		{
			jmp_node[i][j] = jmp_node[i-1][jmp_node[i-1][j]];
			jmp_dis[i][j] = jmp_dis[i-1][j] + jmp_dis[i-1][jmp_node[i-1][j]];
		}
}
 
long long Query(int s, int x[], int t, int y[])
{
	long long ans = 1e15;
	queue<int> cleaner;
	for(int i=0 ; i<s ; i++)
	{
		int u = x[i]+1;
		while(true)
		{
			if(!visit[u])
			{
				cleaner.push(u);
				visit[u] = true;
			}
			dis[u] = min(dis[u], get_dis(x[i]+1, u));
			u = pa[u];
			if(!u) break;
		}
	}
	for(int i=0 ; i<t ; i++)
	{
		int u = y[i]+1;
		while(true)
		{
			if(visit[u]) ans = min(ans, dis[u] + get_dis(y[i], u));
			u = pa[u];
			if(!u) break;
		}
	}
	while(!cleaner.empty())
	{
		visit[cleaner.front()] = true;
		cleaner.pop();
	}
	return ans;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8048 ms 12492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8064 ms 12108 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8048 ms 12492 KB Time limit exceeded
2 Halted 0 ms 0 KB -