oj.uz

Submission #969739

# Submission time Handle Problem Language Result Execution time Memory
969739 2024-04-25T14:13:54 Z starchan Factories (JOI14_factories) C++17
100 / 100
 5133 ms 212208 KB 
#include<bits/stdc++.h>
#include "factories.h"
using namespace std;
#define ll long long
#define in array<ll, 2>
#define pb push_back
#define pob pop_back
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)

const int	 MX			 =		        5e5+5;
const int	 LOGM		 =			       19;
const ll	 INF		 =	             1e18;

vector<ll> d(MX, INF);

vector<in> adj[MX], edge[MX];
int pa[LOGM][MX];
int tin[MX], tout[MX];

ll dep[MX];

int timer; 

void dfs(int u, ll lvl)
{
	tin[u] = ++timer;
	dep[u] = lvl;
	for(int i = 1; i < LOGM; i++)
		pa[i][u] = pa[i-1][pa[i-1][u]];
	for(auto [v, w]: adj[u])
	{
		if(v == pa[0][u])
			continue;
		pa[0][v] = u;
		dfs(v, lvl+w);
	}
	tout[u] = timer;
	return;
}

int lca(int u, int v)
{
	if(tin[u] >= tin[v])
		swap(u, v);
	if(tout[u] >= tout[v])
		return u;
	for(int i = LOGM-1; i >= 0; i--)
	{
		int p = pa[i][u];
		if(tout[p] >= tout[v])
			continue;
		u = p;
	}
	return pa[0][u];
}

void Init(int n, int a[], int b[], int d[])
{
	for(int i = 0; i < n-1; i++)
	{
		adj[a[i]+1].pb({b[i]+1, d[i]});
		adj[b[i]+1].pb({a[i]+1, d[i]});
	}

	timer = 0;
	tin[0] = -1; tout[0] = n+1;
	pa[0][0] = 0; pa[0][1] = 0;
	dfs(1, 0);
	return;
}

ll Query(signed a, signed X[], signed b, signed Y[])
{
	for(int i = 0; i < a; i++)
		X[i]++;
	for(int i = 0; i < b; i++)
		Y[i]++;
	priority_queue<in> pq;

	vector<in> vv;
	for(int i = 0; i < a; i++)
	{
		d[X[i]] = 0;
		pq.push({0ll, X[i]});
		vv.pb({tin[X[i]], X[i]});
	}
	for(int i = 0; i < b; i++)
		vv.pb({tin[Y[i]], Y[i]});
	sort(vv.begin(), vv.end());
	for(int i = 1; i < (a+b); i++)
	{
		int w = lca(vv[i][1], vv[i-1][1]);
		vv.pb({tin[w], w});
	}


	vector<int> path;
	sort(vv.begin(), vv.end()); path.pb(vv[0][1]);
	for(int i = 1; i < vv.size(); i++)
	{
		while(tout[path.back()] < tout[vv[i][1]])
			path.pob();
		int u =	path.back();
		int v = vv[i][1];
		path.pb(v);
		edge[u].pb({v, dep[v]-dep[u]});
		edge[v].pb({u, dep[v]-dep[u]});
	}

	while(pq.size())
	{
		auto [W, u] = pq.top(); W = -W;
		pq.pop();
		if(d[u] < W)
			continue;
		for(auto [v, w]: edge[u])
		{
			if(d[v] > (d[u] + w))
			{
				d[v] = d[u] + w;
				pq.push({-d[v], v});
			}
		}
	}
	ll ans = 1e18;
	for(int i = 0; i < b; i++)
		ans = min(ans, d[Y[i]]);
	for(auto [t, W]: vv)
	{
		d[W] = INF;
		edge[W].clear();
	} 
	return ans;
}

Compilation message

factories.cpp: In function 'long long int Query(int, int*, int, int*)':
factories.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i = 1; i < vv.size(); i++)
      |                 ~~^~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 88664 KB Output is correct
2 Correct 1142 ms 103388 KB Output is correct
3 Correct 1136 ms 103084 KB Output is correct
4 Correct 1078 ms 103392 KB Output is correct
5 Correct 887 ms 103248 KB Output is correct
6 Correct 878 ms 103000 KB Output is correct
7 Correct 1018 ms 103116 KB Output is correct
8 Correct 1028 ms 103196 KB Output is correct
9 Correct 894 ms 103660 KB Output is correct
10 Correct 882 ms 102900 KB Output is correct
11 Correct 1014 ms 102996 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 88408 KB Output is correct
2 Correct 2469 ms 153984 KB Output is correct
3 Correct 2631 ms 158028 KB Output is correct
4 Correct 2448 ms 150892 KB Output is correct
5 Correct 1402 ms 199192 KB Output is correct
6 Correct 2719 ms 159608 KB Output is correct
7 Correct 1764 ms 118496 KB Output is correct
8 Correct 1420 ms 117440 KB Output is correct
9 Correct 841 ms 125780 KB Output is correct
10 Correct 1852 ms 119188 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 88664 KB Output is correct
2 Correct 1142 ms 103388 KB Output is correct
3 Correct 1136 ms 103084 KB Output is correct
4 Correct 1078 ms 103392 KB Output is correct
5 Correct 887 ms 103248 KB Output is correct
6 Correct 878 ms 103000 KB Output is correct
7 Correct 1018 ms 103116 KB Output is correct
8 Correct 1028 ms 103196 KB Output is correct
9 Correct 894 ms 103660 KB Output is correct
10 Correct 882 ms 102900 KB Output is correct
11 Correct 1014 ms 102996 KB Output is correct
12 Correct 17 ms 88408 KB Output is correct
13 Correct 2469 ms 153984 KB Output is correct
14 Correct 2631 ms 158028 KB Output is correct
15 Correct 2448 ms 150892 KB Output is correct
16 Correct 1402 ms 199192 KB Output is correct
17 Correct 2719 ms 159608 KB Output is correct
18 Correct 1764 ms 118496 KB Output is correct
19 Correct 1420 ms 117440 KB Output is correct
20 Correct 841 ms 125780 KB Output is correct
21 Correct 1852 ms 119188 KB Output is correct
22 Correct 5032 ms 179612 KB Output is correct
23 Correct 4626 ms 176456 KB Output is correct
24 Correct 5133 ms 188680 KB Output is correct
25 Correct 4886 ms 187120 KB Output is correct
26 Correct 4839 ms 168484 KB Output is correct
27 Correct 2384 ms 212208 KB Output is correct
28 Correct 4033 ms 170860 KB Output is correct
29 Correct 4751 ms 166068 KB Output is correct
30 Correct 4696 ms 165648 KB Output is correct
31 Correct 4954 ms 165904 KB Output is correct
32 Correct 1286 ms 134968 KB Output is correct
33 Correct 1580 ms 131828 KB Output is correct
34 Correct 2203 ms 119400 KB Output is correct
35 Correct 2023 ms 119156 KB Output is correct
36 Correct 2050 ms 119936 KB Output is correct
37 Correct 2112 ms 119760 KB Output is correct