Submission #354337

#	Time	Username	Problem	Language	Result	Execution time	Memory
354337		Kenzo_1114	Factories (JOI14_factories)	C++17	100 / 100	6400 ms	207980 KiB

factories

#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
const int MAXN = 500010;
const int MAXK = 21;
const long long int INF = 2e18;

int n, q, n_cur, sub[MAXN], par[MAXN], depth[MAXN];
long long int dist[MAXK][MAXN], s[MAXN];
vector<int> graph[MAXN], cost[MAXN];
bool marc[MAXN];

void find_sub(int v, int p)
{
	sub[v] = 1;
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		find_sub(u, v), sub[v] += sub[u];
	}
}

int find_centroid(int v, int p)
{
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		if(u == p || marc[u])	continue;
		if(2 * sub[u] >= n_cur)	return find_centroid(u, v);
	}

	return v;
}

void find_dist(int v, int p, int l, long long int d)
{
	dist[l][v] = d;
//	printf("dist[%d][%d] = %lld\n", l, v, dist[l][v]);
	for(int i = 0; i < (int) graph[v].size(); i++)
	{
		int u = graph[v][i];
		int w = cost[v][i];
		if(u == p || marc[u])	continue;
		find_dist(u, v, l, d + w);	
	}
}

void decompose(int v, int p, int level)
{
	find_sub(v, p);
	n_cur = sub[v];
	int centroid = find_centroid(v, p);

//	printf("centroid = %d\n", centroid);
	marc[centroid] = true;
	par[centroid] = (v == p) ? centroid : p;
	depth[centroid] = level;

	find_dist(centroid, centroid, level, 0);

	for(int i = 0; i < (int) graph[centroid].size(); i++)
	{
		int u = graph[centroid][i];
		if(!marc[u])	decompose(u, centroid, level + 1);
	}
}

void Init(int N, int A[], int B[], int D[])
{
	n = N;
	for(int i = 0; i < n; i++)	s[i] = INF;

	for(int i = 0; i < n - 1; i++)
	{
		int a = A[i], b = B[i], d = D[i];
		graph[a].push_back(b);
		graph[b].push_back(a);
		cost[a].push_back(d);
		cost[b].push_back(d);
	}

	decompose(0, 0, 0);
}

void upd(int v, bool flag)
{
	int cur = v;

	if(flag)	s[cur] = 0;
	else		s[cur] = INF;
	
	while(cur != par[cur])
	{
		cur = par[cur];
		if(flag)	s[cur] = min(s[cur], dist[depth[cur]][v]);
		else		s[cur] = INF;
	}
}

long long int qry(int v)
{
	int cur = v;
	long long int ans = s[cur];

	while(cur != par[cur])
	{
		cur = par[cur];
		ans = min(ans, s[cur] + dist[depth[cur]][v]);
	}

	return ans;
}

long long int Query(int S, int X[], int T, int Y[])
{
	for(int i = 0; i < S; i++)	upd(X[i], true);
	
	long long int ans = INF;
	for(int i = 0; i < T; i++)	ans = min(ans, qry(Y[i]));
	for(int i = 0; i < S; i++)	upd(X[i], false);

	return ans;
}

• Subtask 1: 15 / 15
• Subtask 2: 18 / 18
• Subtask 3: 67 / 67