Submission #103826

#	Time	Username	Problem	Language	Result	Execution time	Memory
103826		igba	Factories (JOI14_factories)	C++17	15 / 100	8113 ms	443300 KiB

factories

#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
#define mkp make_pair
const int MAXN = 5 * 100100, MAXLN = 20;
const long long LINF = 0x3f3f3f3f3f3f3f3f;
int n, sz[MAXN], cdp[MAXN];
long long aux[MAXN];
bool rmd[MAXN], flg[MAXN];
vector<pair<int, int>> g[MAXN];
unordered_map<int, long long> dist[MAXN];
 
void szdfs(int v, int p = -1)
{
	sz[v] = 1;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u])
			szdfs(u, v), sz[v] += sz[u];
}
 
int getCentroid(int v, int p = -1, int rt = -1)
{
	if(rt == -1)
		rt = v;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u] && sz[u] > sz[rt] / 2)
			return getCentroid(u, v, rt);
	return v;
}

void distdfs(int v, int rt, long long d = 0, int p = -1)
{
	dist[rt][v] = d;
	for(const auto&[w, u] : g[v])
		if(u != p && !rmd[u])
			distdfs(u, rt, d + w, v);
}

void cd(int v, int cp = -1)
{
	szdfs(v);
	int c = getCentroid(v);
	distdfs(c, c);
	cdp[c] = cp, rmd[c] = true;
	for(const auto&[w, u] : g[c])
		if(!rmd[u])
			cd(u, c);
}
 
void Init(int N, int A[], int B[], int D[])
{
	n = N;
	for(int i = 0; i < n - 1; ++i)
		g[A[i]].push_back(mkp(D[i], B[i])), g[B[i]].push_back(mkp(D[i], A[i]));
	for(int i = 0; i < n; ++i)
		aux[i] = LINF;
	cd(0);
}
 
long long Query(int S, int X[], int T, int Y[])
{
	long long ans = LINF;
	vector<int> s;
	for(int i = 0, cur; i < S; ++i)
	{
		cur = X[i];
		while(cur != -1)
		{
			if(!flg[cur])
				s.push_back(cur);
			flg[cur] = true;
			aux[cur] = min(aux[cur], dist[cur][X[i]]);
			cur = cdp[cur];
		}
	}
	for(int i = 0, cur; i < T; ++i)
	{
		cur = Y[i];
		while(cur != -1)
		{
			ans = min(ans, aux[cur] + dist[cur][Y[i]]);
			cur = cdp[cur];
		}
	}
	for(const int& x : s)
		aux[x] = LINF, flg[x] = false;
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void szdfs(int, int)':
factories.cpp:17:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[v])
                      ^
factories.cpp: In function 'int getCentroid(int, int, int)':
factories.cpp:26:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[v])
                      ^
factories.cpp: In function 'void cd(int, int)':
factories.cpp:46:22: warning: unused variable 'w' [-Wunused-variable]
  for(const auto&[w, u] : g[c])
                      ^

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