oj.uz

Submission #958504

# Submission time Handle Problem Language Result Execution time Memory
958504 2024-04-05T22:36:23 Z JwFXoiz Factories (JOI14_factories) C++14
15 / 100
 8000 ms 158056 KB 
#include <bits/stdc++.h>
#include "factories.h"
 
using namespace std;
 
#define inf 0x3F3F3F3F3F3F3F3F
 
const int MXN = 5e5 + 5;
const int LOG = 21;
const int B = 600;
 
int n;
vector<array<long long, 2>> adj[MXN];
long long dist[MXN], dep[MXN];
long long p[LOG][MXN];
long long in[MXN], out[MXN], tim = -1;
 
void dfs(int a)
{
	in[a] = ++tim;
	for (array<long long, 2> &v : adj[a])
	{
		if (v[0] == p[0][a]) continue;
		dep[v[0]] = dep[a] + v[1];
		p[0][v[0]] = a;
		dfs(v[0]);
	}
	out[a] = tim;
}
 
void Init(int N, int A[], int B[], int D[]) 
{
	for (int i = 0; i < n; i++)
	{
		adj[i].clear();
		dist[i] = dep[i] = 0;
		for (int j = 0; j < LOG; j++) p[j][i] = 0;
		in[i] = out[i] = 0;
	}
	n = N;
	for (int i = 0; i < n - 1; i++)
	{
		adj[A[i]].push_back({B[i], D[i]});
		adj[B[i]].push_back({A[i], D[i]});
	}
	p[0][0] = 0;
	dfs(0);
	for (int i = 1; i < LOG; i++) for (int j = 0; j < n; j++) p[i][j] = p[i - 1][p[i - 1][j]];
}
 
void bfs(vector<int> &s)
{
	for (int i = 0; i < n; i++) dist[i] = inf;
	priority_queue<array<long long, 2>, vector<array<long long, 2>>, greater<array<long long, 2>>> pq;
	for (int x : s)
	{
		dist[x] = 0;
		pq.push({0, x});
	} 
	while (!pq.empty())
	{
		array<long long, 2> f = pq.top();
		pq.pop();
		if (f[0] > dist[f[1]]) continue;
		for (array<long long, 2> &v : adj[f[1]])
		{
			if (dist[v[0]] > f[0] + v[1])
			{
				dist[v[0]] = f[0] + v[1];
				pq.push({dist[v[0]], v[0]});
			}
		}
	}
}
 
int anc(int u, int v)
{
	return in[u] <= in[v] && out[v] <= out[u];
}
 
int LCA(int u, int v)
{
	if (anc(u, v)) return u;
	if (anc(v, u)) return v;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (anc(p[i][u], v)) continue;
		u = p[i][u];
	}
	return p[0][u];
}
 
long long DIST(int u, int v)
{
	return dep[u] + dep[v] - 2 * dep[LCA(u, v)];
}
 
long long Query(int S, int X[], int T, int Y[]) 
{
	vector<int> v[2];
	for (int i = 0; i < S; i++) v[0].push_back(X[i]);
	for (int i = 0; i < T; i++) v[1].push_back(Y[i]);
	long long res = inf;
	if (max(S, T) >= 1) 
	{
		bfs(v[0]);
		for (int x : v[1]) res = min(res, dist[x]);
	}
	else
	{
		for (int x : v[0])
		{
			for (int y : v[1])
			{
				res = min(res, DIST(x, y));
			}
		}
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78424 KB Output is correct
2 Correct 2566 ms 84976 KB Output is correct
3 Correct 2515 ms 84816 KB Output is correct
4 Correct 1956 ms 94568 KB Output is correct
5 Correct 1515 ms 94676 KB Output is correct
6 Correct 2937 ms 94568 KB Output is correct
7 Correct 2511 ms 94420 KB Output is correct
8 Correct 2399 ms 94444 KB Output is correct
9 Correct 1496 ms 94808 KB Output is correct
10 Correct 2910 ms 95136 KB Output is correct
11 Correct 2528 ms 94548 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 78372 KB Output is correct
2 Execution timed out 8068 ms 158056 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 78424 KB Output is correct
2 Correct 2566 ms 84976 KB Output is correct
3 Correct 2515 ms 84816 KB Output is correct
4 Correct 1956 ms 94568 KB Output is correct
5 Correct 1515 ms 94676 KB Output is correct
6 Correct 2937 ms 94568 KB Output is correct
7 Correct 2511 ms 94420 KB Output is correct
8 Correct 2399 ms 94444 KB Output is correct
9 Correct 1496 ms 94808 KB Output is correct
10 Correct 2910 ms 95136 KB Output is correct
11 Correct 2528 ms 94548 KB Output is correct
12 Correct 40 ms 78372 KB Output is correct
13 Execution timed out 8068 ms 158056 KB Time limit exceeded
14 Halted 0 ms 0 KB -