Submission #552739

#	Time	Username	Problem	Language	Result	Execution time	Memory
552739		Hanksburger	Factories (JOI14_factories)	C++17	33 / 100	8099 ms	177984 KiB

factories

#include "factories.h"
#include <bits/stdc++.h>
using namespace std;
long long par[20][500005], dist[500005], depth[500005], mp[500005], exist[500005], d[500005], cnt, sz;
vector<pair<long long, long long> > adj[500005];
priority_queue<pair<long long, long long> > pq;
vector<long long> vec, vec2, vec3;
bool visited[500005];
long long lca(long long u, long long v)
{
	if (depth[u]>depth[v])
		swap(u, v);
	long long cur=depth[v]-depth[u];
	for (long long i=19; i>=0; i--)
		if (cur&(1<<i))
			v=par[i][v];
	if (u==v)
		return u;
	for (long long i=19; i>=0; i--)
	{
		if (par[i][u]!=par[i][v])
		{
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}
void dfs(long long u, long long p, long long dis, long long dep)
{
	mp[u]=cnt;
	cnt++;
	par[0][mp[u]]=mp[p];
	dist[mp[u]]=dis;
	depth[mp[u]]=dep;
	for (long long i=0; i<adj[u].size(); i++)
	{
		long long v=adj[u][i].first, w=adj[u][i].second;
		if (v!=p)
			dfs(v, u, dis+w, dep+1);
	}
}
void dfs2(long long ind)
{
	long long u=vec3[ind];
	while (cnt<sz && lca(u, vec3[cnt])==u)
	{
		long long v=vec3[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 (long long 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 (long long i=1; i<=19; i++)
		for (long long j=0; j<N; j++)
			par[i][j]=par[i-1][par[i-1][j]];
	for (long long i=0; i<N; i++)
		adj[i].clear();
}
long long Query(int S, int X[], int T, int Y[])
{
//	cout << "Query\n";
	vec.clear();
	vec2.clear();
	vec3.clear();
	for (long long i=0; i<S; i++)
	{
		X[i]=mp[X[i]];
		vec.push_back(X[i]);
	}
	for (long long i=0; i<T; i++)
	{
		Y[i]=mp[Y[i]];
		vec.push_back(Y[i]);
	}
	sort(vec.begin(), vec.end());
	for (long long i=0; i<=vec.size()-2; i++)
	{
		vec2.push_back(lca(vec[i], vec[i+1]));
		exist[vec2[i]]=i+1;
	}
	for (long long i=0; i<=vec.size()-2; i++)
	{
		if (!exist[vec[i]])
		{
			vec3.push_back(vec[i]);
			vec3.push_back(vec2[i]);
		}
		else if (exist[vec[i]]==i+1)
			vec3.push_back(vec[i]);
	}
	vec3.push_back(vec[vec.size()-1]);
	sort(vec3.begin(), vec3.end());
	for (long long i=0; i<vec2.size(); i++)
		exist[vec2[i]]=0;
/*	cout << "vec:  ";
	for (long long i=0; i<vec.size(); i++)
		cout << vec[i] << ' ';
	cout << '\n';
	cout << "vec2: ";
	for (long long i=0; i<vec2.size(); i++)
		cout << vec2[i] << ' ';
	cout << '\n';
	cout << "vec3: ";
	for (long long i=0; i<vec3.size(); i++)
		cout << vec3[i] << ' ';
	cout << '\n'; */
	sz=vec3.size();
	cnt=1;
	dfs2(0);
/*	for (long long i=0; i<vec3.size(); i++)
	{
		cout << "adj " << vec3[i] << ": ";
		for (long long j=0; j<adj[vec3[i]].size(); j++)
			cout << adj[vec3[i]][j].first << ' ';
		cout << '\n';
	} */
	for (long long i=0; i<sz; i++)
	{
		d[vec3[i]]=1e18;
		visited[vec3[i]]=0;
	}
	for (long long i=0; i<S; i++)
	{
		d[X[i]]=0;
		pq.push({0, X[i]});
	}
	while (!pq.empty())
	{
		long long u=pq.top().second;
		pq.pop();
		if (visited[u])
			continue;
		visited[u]=1;
		for (long long i=0; i<adj[u].size(); i++)
		{
			long long v=adj[u][i].first, 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 (long long i=0; i<T; i++)
		ans=min(ans, d[Y[i]]);
	for (long long i=0; i<sz; i++)
		adj[vec3[i]].clear();
	return ans;
}

Compilation message (stderr)

factories.cpp: In function 'void dfs(long long int, long long int, long long int, long long int)':
factories.cpp:36:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for (long long i=0; i<adj[u].size(); i++)
      |                      ~^~~~~~~~~~~~~~
factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:87:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for (long long i=0; i<=vec.size()-2; i++)
      |                      ~^~~~~~~~~~~~~~
factories.cpp:92:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |  for (long long i=0; i<=vec.size()-2; i++)
      |                      ~^~~~~~~~~~~~~~
factories.cpp:104:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |  for (long long i=0; i<vec2.size(); i++)
      |                      ~^~~~~~~~~~~~
factories.cpp:145:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |   for (long long i=0; i<adj[u].size(); i++)
      |                       ~^~~~~~~~~~~~~~

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