oj.uz

Submission #890100

# Submission time Handle Problem Language Result Execution time Memory
890100 2023-12-20T14:19:07 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 = 175;
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 35676 KB Output is correct
2 Correct 465 ms 47260 KB Output is correct
3 Correct 954 ms 46980 KB Output is correct
4 Correct 328 ms 47088 KB Output is correct
5 Correct 558 ms 47188 KB Output is correct
6 Correct 810 ms 46988 KB Output is correct
7 Correct 974 ms 46984 KB Output is correct
8 Correct 1125 ms 46996 KB Output is correct
9 Correct 551 ms 47156 KB Output is correct
10 Correct 797 ms 46996 KB Output is correct
11 Correct 1025 ms 47108 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35416 KB Output is correct
2 Correct 1210 ms 196680 KB Output is correct
3 Correct 2234 ms 189092 KB Output is correct
4 Correct 834 ms 187808 KB Output is correct
5 Correct 3063 ms 204560 KB Output is correct
6 Correct 1855 ms 189128 KB Output is correct
7 Correct 1973 ms 69260 KB Output is correct
8 Correct 977 ms 69292 KB Output is correct
9 Correct 2860 ms 71204 KB Output is correct
10 Correct 1422 ms 69760 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35676 KB Output is correct
2 Correct 465 ms 47260 KB Output is correct
3 Correct 954 ms 46980 KB Output is correct
4 Correct 328 ms 47088 KB Output is correct
5 Correct 558 ms 47188 KB Output is correct
6 Correct 810 ms 46988 KB Output is correct
7 Correct 974 ms 46984 KB Output is correct
8 Correct 1125 ms 46996 KB Output is correct
9 Correct 551 ms 47156 KB Output is correct
10 Correct 797 ms 46996 KB Output is correct
11 Correct 1025 ms 47108 KB Output is correct
12 Correct 7 ms 35416 KB Output is correct
13 Correct 1210 ms 196680 KB Output is correct
14 Correct 2234 ms 189092 KB Output is correct
15 Correct 834 ms 187808 KB Output is correct
16 Correct 3063 ms 204560 KB Output is correct
17 Correct 1855 ms 189128 KB Output is correct
18 Correct 1973 ms 69260 KB Output is correct
19 Correct 977 ms 69292 KB Output is correct
20 Correct 2860 ms 71204 KB Output is correct
21 Correct 1422 ms 69760 KB Output is correct
22 Correct 4388 ms 188220 KB Output is correct
23 Correct 2868 ms 189264 KB Output is correct
24 Correct 6899 ms 189720 KB Output is correct
25 Correct 6636 ms 191460 KB Output is correct
26 Execution timed out 8100 ms 190036 KB Time limit exceeded
27 Halted 0 ms 0 KB -