oj.uz

답안 #311939

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
311939 2020-10-12T03:31:27 Z T0p_ 공장들 (JOI14_factories) C++14
0 / 100
 8000 ms 63152 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 root;
int sz[N], pa[N], lv[N], jmp_node[20][N];
long long dis[N], jmp_dis[20][N];
bool visit[N];
vector<GRAPH> g[N];
queue<int> bt;

int get_sz(int u, int p)
{
	sz[u] = 1;
	for(auto x : g[u])
		if(x.node != p) 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 nu = 0, nf = 0;
	for(auto x : g[u])
	{
		if(visit[x.node] || x.node == p) continue ;
		if(sz[x.node] > n/2)
		{
			ch = false;
			if(sz[x.node] > nf)
			{
				nf = sz[x.node];
				nu = x.node;
			}
		}
	}
	return (ch) ? u : get_centroid(nu, 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);
	}
}

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

long long Query(int s, int x[], int t, int y[])
{
	long long ans = 1e15;
	for(int i=0 ; i<s ; i++)
	{
		int now = x[i]+1;
		while(true)
		{
			if(!now) break ;
			dis[now] = min(dis[now], get_dis(x[i]+1, now));
			if(!visit[now])
			{
				bt.push(now);
				visit[now] = true;
			}
			now = pa[now];
		}
	}
	for(int i=0 ; i<t ; i++)
	{
		int now = y[i]+1;
		while(true)
		{
			if(!now) break ;
			ans = min(ans, get_dis(y[i]+1, now) + dis[now]);
			now = pa[now];
		}
	}
	while(!bt.empty())
	{
		visit[bt.front()] = false;
		dis[bt.front()] = 1e15;
		bt.pop();
	}
	return ans;
}

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 13048 KB Output is correct
2 Correct 1432 ms 31620 KB Output is correct
3 Execution timed out 8047 ms 31608 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12800 KB Output is correct
2 Execution timed out 8083 ms 63152 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 13048 KB Output is correct
2 Correct 1432 ms 31620 KB Output is correct
3 Execution timed out 8047 ms 31608 KB Time limit exceeded
4 Halted 0 ms 0 KB -