oj.uz

Submission #890101

# Submission time Handle Problem Language Result Execution time Memory
890101 2023-12-20T14:21:54 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204560 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("Ofast")
using namespace std;

const int N = 5e5 + 55, L = 2e0 + 20, Q = 185;
const long long I = 1e18 + 118;
int n, q, h[N], par[N][L];
long long ans, spt[N][L], dis[N];
vector<pair<int, int>> adj[N];

void dfs(int v, int p) {
	for (int i = 0; i < adj[v].size(); i++) {
		int u = adj[v][i].first, w = adj[v][i].second;
		if (u == p) {
			swap(adj[v].back(), adj[v][i]);
			adj[v].pop_back();
			if (i == adj[v].size())
				return;
			u = adj[v][i].first, w = adj[v][i].second;
		}

		par[u][0] = v;
		spt[u][0] = w;
		h[u] = h[v] + 1;
		dfs(u, v);
	}
}

void dfsu(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dfsu(u, v);
		dis[v] = min(dis[v], dis[u] + w);
	}
}

void dfsd(int v, int p) {
	for (auto [u, w]: adj[v]) {
		dis[u] = min(dis[u], dis[v] + w);
		dfsd(u, v);
	}
}

long long distance(int v, int u) {
	long long res = 0;
	if (h[v] < h[u]) swap(v, u);
	for (int i = 0; i < L && res < ans; i++)
		if ((1 << i) & (h[v] - h[u])) {
			res += spt[v][i];
			v = par[v][i];
		}
	if (v == u) return res;

	for (int i = L - 1; i >= 0 && res < ans; i--)
		if (par[v][i] != par[u][i]) {
			res += spt[v][i] + spt[u][i];
			v = par[v][i];
			u = par[u][i];
		}
	return res + spt[v][0] + spt[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		adj[A[i] + 1].push_back({B[i] + 1, D[i]});
		adj[B[i] + 1].push_back({A[i] + 1, D[i]});
	}

	dfs(1, 0);
	for (int i = 1; i < L; i++)
		for (int j = 1; j <= n; j++) {
			par[j][i] = par[par[j][i - 1]][i - 1];
			spt[j][i] = spt[j][i - 1] + spt[par[j][i - 1]][i - 1];
		}
}

long long Query(int S, int X[], int T, int Y[]) {
	ans = I;
	if (S < Q) {
		for (int i = 0; i < T; i++)
			for (int j = 0; j < S; j++)
				ans = min(ans, distance(Y[i] + 1, X[j] + 1));
		return ans;
	}
	
	for (int i = 0; i < N; dis[i++] = I);
	for (int i = 0; i < S; dis[X[i++] + 1] = 0); 
	dfsu(1, 0);
	dfsd(1, 0);

	for (int i = 0; i < T; i++)
		ans = min(ans, dis[Y[i] + 1]);
	return ans;
}

Compilation message

factories.cpp: In function 'void dfs(int, int)':
factories.cpp:13:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
factories.cpp:18:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |    if (i == adj[v].size())
      |        ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35420 KB Output is correct
2 Correct 480 ms 41808 KB Output is correct
3 Correct 975 ms 41880 KB Output is correct
4 Correct 300 ms 41860 KB Output is correct
5 Correct 577 ms 42020 KB Output is correct
6 Correct 832 ms 41864 KB Output is correct
7 Correct 945 ms 41868 KB Output is correct
8 Correct 1104 ms 41864 KB Output is correct
9 Correct 601 ms 41868 KB Output is correct
10 Correct 846 ms 42068 KB Output is correct
11 Correct 966 ms 41860 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35420 KB Output is correct
2 Correct 1196 ms 186976 KB Output is correct
3 Correct 2078 ms 188908 KB Output is correct
4 Correct 828 ms 187812 KB Output is correct
5 Correct 2895 ms 204560 KB Output is correct
6 Correct 1811 ms 189400 KB Output is correct
7 Correct 1812 ms 69508 KB Output is correct
8 Correct 918 ms 69332 KB Output is correct
9 Correct 2685 ms 71300 KB Output is correct
10 Correct 1354 ms 69700 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35420 KB Output is correct
2 Correct 480 ms 41808 KB Output is correct
3 Correct 975 ms 41880 KB Output is correct
4 Correct 300 ms 41860 KB Output is correct
5 Correct 577 ms 42020 KB Output is correct
6 Correct 832 ms 41864 KB Output is correct
7 Correct 945 ms 41868 KB Output is correct
8 Correct 1104 ms 41864 KB Output is correct
9 Correct 601 ms 41868 KB Output is correct
10 Correct 846 ms 42068 KB Output is correct
11 Correct 966 ms 41860 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1196 ms 186976 KB Output is correct
14 Correct 2078 ms 188908 KB Output is correct
15 Correct 828 ms 187812 KB Output is correct
16 Correct 2895 ms 204560 KB Output is correct
17 Correct 1811 ms 189400 KB Output is correct
18 Correct 1812 ms 69508 KB Output is correct
19 Correct 918 ms 69332 KB Output is correct
20 Correct 2685 ms 71300 KB Output is correct
21 Correct 1354 ms 69700 KB Output is correct
22 Correct 4264 ms 188216 KB Output is correct
23 Correct 2784 ms 189236 KB Output is correct
24 Correct 6304 ms 189520 KB Output is correct
25 Correct 6121 ms 191440 KB Output is correct
26 Execution timed out 8007 ms 189976 KB Time limit exceeded
27 Halted 0 ms 0 KB -