oj.uz

Submission #552741

# Submission time Handle Problem Language Result Execution time Memory
552741 2022-04-23T19:19:31 Z Hanksburger Factories (JOI14_factories) C++17
100 / 100
 5134 ms 133732 KB 
#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

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12780 KB Output is correct
2 Correct 1169 ms 21840 KB Output is correct
3 Correct 1263 ms 21972 KB Output is correct
4 Correct 1121 ms 22128 KB Output is correct
5 Correct 979 ms 21992 KB Output is correct
6 Correct 775 ms 21720 KB Output is correct
7 Correct 1318 ms 21732 KB Output is correct
8 Correct 1174 ms 21712 KB Output is correct
9 Correct 981 ms 22004 KB Output is correct
10 Correct 830 ms 21740 KB Output is correct
11 Correct 1313 ms 21732 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12372 KB Output is correct
2 Correct 2052 ms 100608 KB Output is correct
3 Correct 2710 ms 104844 KB Output is correct
4 Correct 1272 ms 97816 KB Output is correct
5 Correct 1994 ms 127552 KB Output is correct
6 Correct 2857 ms 106192 KB Output is correct
7 Correct 2510 ms 39080 KB Output is correct
8 Correct 1414 ms 38428 KB Output is correct
9 Correct 1837 ms 42492 KB Output is correct
10 Correct 2616 ms 40364 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 12780 KB Output is correct
2 Correct 1169 ms 21840 KB Output is correct
3 Correct 1263 ms 21972 KB Output is correct
4 Correct 1121 ms 22128 KB Output is correct
5 Correct 979 ms 21992 KB Output is correct
6 Correct 775 ms 21720 KB Output is correct
7 Correct 1318 ms 21732 KB Output is correct
8 Correct 1174 ms 21712 KB Output is correct
9 Correct 981 ms 22004 KB Output is correct
10 Correct 830 ms 21740 KB Output is correct
11 Correct 1313 ms 21732 KB Output is correct
12 Correct 11 ms 12372 KB Output is correct
13 Correct 2052 ms 100608 KB Output is correct
14 Correct 2710 ms 104844 KB Output is correct
15 Correct 1272 ms 97816 KB Output is correct
16 Correct 1994 ms 127552 KB Output is correct
17 Correct 2857 ms 106192 KB Output is correct
18 Correct 2510 ms 39080 KB Output is correct
19 Correct 1414 ms 38428 KB Output is correct
20 Correct 1837 ms 42492 KB Output is correct
21 Correct 2616 ms 40364 KB Output is correct
22 Correct 3206 ms 109528 KB Output is correct
23 Correct 3329 ms 111604 KB Output is correct
24 Correct 3421 ms 111976 KB Output is correct
25 Correct 3483 ms 115204 KB Output is correct
26 Correct 5134 ms 108496 KB Output is correct
27 Correct 2665 ms 133732 KB Output is correct
28 Correct 2039 ms 112460 KB Output is correct
29 Correct 4761 ms 112812 KB Output is correct
30 Correct 4759 ms 112356 KB Output is correct
31 Correct 4720 ms 113952 KB Output is correct
32 Correct 1643 ms 59680 KB Output is correct
33 Correct 1212 ms 57960 KB Output is correct
34 Correct 2859 ms 51236 KB Output is correct
35 Correct 2497 ms 51128 KB Output is correct
36 Correct 2610 ms 51768 KB Output is correct
37 Correct 2699 ms 51704 KB Output is correct