Submission #552741

#	Time	Username	Problem	Language	Result	Execution time	Memory
552741		Hanksburger	Factories (JOI14_factories)	C++17	100 / 100	5134 ms	133732 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
int par[19][500005], depth[500005], mp[500005], cnt, sz;
vector<pair<int, long long> > adj[500005];
priority_queue<pair<long long, int> > pq;
long long dist[500005], d[500005];
bool visited[500005];
vector<int> vec;
int lca(int u, int v)
{
	if (depth[u]>depth[v])
		swap(u, v);
	int cur=depth[v]-depth[u];
	for (int i=18; i>=0; i--)
		if (cur&(1<<i))
			v=par[i][v];
	if (u==v)
		return u;
	for (int i=18; i>=0; i--)
	{
		if (par[i][u]!=par[i][v])
		{
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}
void dfs(int u, int p, long long dis, int dep)
{
	mp[u]=cnt;
	cnt++;
	par[0][mp[u]]=mp[p];
	dist[mp[u]]=dis;
	depth[mp[u]]=dep;
	for (int i=0; i<adj[u].size(); i++)
	{
		int v=adj[u][i].first;
		long long w=adj[u][i].second;
		if (v!=p)
			dfs(v, u, dis+w, dep+1);
	}
}
void dfs2(int ind)
{
	int u=vec[ind];
	while (cnt<sz && lca(u, vec[cnt])==u)
	{
		int v=vec[cnt];
		long long w=dist[v]-dist[u];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
		cnt++;
		dfs2(cnt-1);
	}
}
void Init(int N, int A[], int B[], int D[])
{
	for (int i=0; i<=N-2; i++)
	{
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	dfs(0, 0, 0, 0);
	for (int i=1; i<=18; i++)
		for (int j=0; j<N; j++)
			par[i][j]=par[i-1][par[i-1][j]];
	for (int i=0; i<N; i++)
		adj[i].clear();
}
long long Query(int S, int X[], int T, int Y[])
{
	vec.clear();
	for (int i=0; i<S; i++)
	{
		X[i]=mp[X[i]];
		vec.push_back(X[i]);
	}
	for (int i=0; i<T; i++)
	{
		Y[i]=mp[Y[i]];
		vec.push_back(Y[i]);
	}
	sort(vec.begin(), vec.end());
	for (int i=1; i<S+T; i++)
		vec.push_back(lca(vec[i-1], vec[i]));
	sort(vec.begin(), vec.end());
	vec.resize(unique(vec.begin(), vec.end())-vec.begin());
	sz=vec.size();
	cnt=1;
	dfs2(0);
	for (int i=0; i<sz; i++)
	{
		d[vec[i]]=1e18;
		visited[vec[i]]=0;
	}
	for (int i=0; i<S; i++)
	{
		d[X[i]]=0;
		pq.push({0, X[i]});
	}
	while (!pq.empty())
	{
		int u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (int i=0; i<adj[u].size(); i++)
		{
			int v=adj[u][i].first;
			long long w=adj[u][i].second;
			if (d[v]>d[u]+w)
			{
				d[v]=d[u]+w;
				pq.push({-d[v], v});
			}
		}
	}
	long long ans=1e18;
	for (int i=0; i<T; i++)
		ans=min(ans, d[Y[i]]);
	for (int i=0; i<sz; i++)
		adj[vec[i]].clear();
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(int, int, long long int, int)':
factories.cpp:37:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |  for (int i=0; i<adj[u].size(); i++)
      |                ~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |   for (int i=0; i<adj[u].size(); i++)
      |                 ~^~~~~~~~~~~~~~

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