oj.uz

Submission #958501

# Submission time Handle Problem Language Result Execution time Memory
958501 2024-04-05T22:33:22 Z JwFXoiz Factories (JOI14_factories) C++14
18 / 100
 8000 ms 143588 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<int, 2>> adj[MXN];
long long dist[MXN], dep[MXN];
int p[LOG][MXN];
int in[MXN], out[MXN], tim = -1;
 
void dfs(int a)
{
	in[a] = ++tim;
	for (array<int, 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<int, 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]);
	if (v[0].size() < v[1].size()) swap(v[0], v[1]);
	long long res = inf;
	if (v[0].size() >= B) 
	{
		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
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 74516 KB Output is correct
2 Correct 2319 ms 81856 KB Output is correct
3 Execution timed out 8007 ms 87116 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 74332 KB Output is correct
2 Correct 2315 ms 117316 KB Output is correct
3 Correct 4284 ms 121956 KB Output is correct
4 Correct 2259 ms 120196 KB Output is correct
5 Correct 1083 ms 143588 KB Output is correct
6 Correct 3583 ms 122320 KB Output is correct
7 Correct 3888 ms 96948 KB Output is correct
8 Correct 1467 ms 96724 KB Output is correct
9 Correct 1147 ms 99668 KB Output is correct
10 Correct 2346 ms 97368 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 74516 KB Output is correct
2 Correct 2319 ms 81856 KB Output is correct
3 Execution timed out 8007 ms 87116 KB Time limit exceeded
4 Halted 0 ms 0 KB -