oj.uz

Submission #890096

# Submission time Handle Problem Language Result Execution time Memory
890096 2023-12-20T14:10:31 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204552 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 35416 KB Output is correct
2 Correct 506 ms 41876 KB Output is correct
3 Correct 998 ms 42064 KB Output is correct
4 Correct 306 ms 41808 KB Output is correct
5 Correct 607 ms 42020 KB Output is correct
6 Correct 883 ms 41880 KB Output is correct
7 Correct 998 ms 41864 KB Output is correct
8 Correct 1107 ms 41868 KB Output is correct
9 Correct 603 ms 41868 KB Output is correct
10 Correct 851 ms 41864 KB Output is correct
11 Correct 990 ms 41872 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 1233 ms 186940 KB Output is correct
3 Correct 2186 ms 188908 KB Output is correct
4 Correct 857 ms 187832 KB Output is correct
5 Correct 3015 ms 204552 KB Output is correct
6 Correct 1953 ms 189120 KB Output is correct
7 Correct 1947 ms 69260 KB Output is correct
8 Correct 992 ms 69300 KB Output is correct
9 Correct 2784 ms 71200 KB Output is correct
10 Correct 1387 ms 69692 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35416 KB Output is correct
2 Correct 506 ms 41876 KB Output is correct
3 Correct 998 ms 42064 KB Output is correct
4 Correct 306 ms 41808 KB Output is correct
5 Correct 607 ms 42020 KB Output is correct
6 Correct 883 ms 41880 KB Output is correct
7 Correct 998 ms 41864 KB Output is correct
8 Correct 1107 ms 41868 KB Output is correct
9 Correct 603 ms 41868 KB Output is correct
10 Correct 851 ms 41864 KB Output is correct
11 Correct 990 ms 41872 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1233 ms 186940 KB Output is correct
14 Correct 2186 ms 188908 KB Output is correct
15 Correct 857 ms 187832 KB Output is correct
16 Correct 3015 ms 204552 KB Output is correct
17 Correct 1953 ms 189120 KB Output is correct
18 Correct 1947 ms 69260 KB Output is correct
19 Correct 992 ms 69300 KB Output is correct
20 Correct 2784 ms 71200 KB Output is correct
21 Correct 1387 ms 69692 KB Output is correct
22 Correct 4392 ms 188252 KB Output is correct
23 Correct 2950 ms 189268 KB Output is correct
24 Correct 6379 ms 189712 KB Output is correct
25 Correct 6496 ms 191452 KB Output is correct
26 Execution timed out 8007 ms 190032 KB Time limit exceeded
27 Halted 0 ms 0 KB -