oj.uz

Submission #890099

# Submission time Handle Problem Language Result Execution time Memory
890099 2023-12-20T14:17:08 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 214284 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("O2,unroll-loops")
#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:14: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]
   14 |  for (int i = 0; i < adj[v].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~
factories.cpp:19: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]
   19 |    if (i == adj[v].size())
      |        ~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35416 KB Output is correct
2 Correct 482 ms 41876 KB Output is correct
3 Correct 990 ms 41856 KB Output is correct
4 Correct 308 ms 41864 KB Output is correct
5 Correct 562 ms 41860 KB Output is correct
6 Correct 844 ms 41856 KB Output is correct
7 Correct 974 ms 41860 KB Output is correct
8 Correct 1085 ms 41864 KB Output is correct
9 Correct 550 ms 42052 KB Output is correct
10 Correct 851 ms 41864 KB Output is correct
11 Correct 997 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 1373 ms 186940 KB Output is correct
3 Correct 2184 ms 198384 KB Output is correct
4 Correct 807 ms 197280 KB Output is correct
5 Correct 2789 ms 214284 KB Output is correct
6 Correct 1843 ms 198980 KB Output is correct
7 Correct 1875 ms 76912 KB Output is correct
8 Correct 1039 ms 76720 KB Output is correct
9 Correct 2854 ms 78672 KB Output is correct
10 Correct 1380 ms 77108 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 35416 KB Output is correct
2 Correct 482 ms 41876 KB Output is correct
3 Correct 990 ms 41856 KB Output is correct
4 Correct 308 ms 41864 KB Output is correct
5 Correct 562 ms 41860 KB Output is correct
6 Correct 844 ms 41856 KB Output is correct
7 Correct 974 ms 41860 KB Output is correct
8 Correct 1085 ms 41864 KB Output is correct
9 Correct 550 ms 42052 KB Output is correct
10 Correct 851 ms 41864 KB Output is correct
11 Correct 997 ms 41860 KB Output is correct
12 Correct 7 ms 35420 KB Output is correct
13 Correct 1373 ms 186940 KB Output is correct
14 Correct 2184 ms 198384 KB Output is correct
15 Correct 807 ms 197280 KB Output is correct
16 Correct 2789 ms 214284 KB Output is correct
17 Correct 1843 ms 198980 KB Output is correct
18 Correct 1875 ms 76912 KB Output is correct
19 Correct 1039 ms 76720 KB Output is correct
20 Correct 2854 ms 78672 KB Output is correct
21 Correct 1380 ms 77108 KB Output is correct
22 Correct 4490 ms 200996 KB Output is correct
23 Correct 2892 ms 202040 KB Output is correct
24 Correct 6524 ms 202260 KB Output is correct
25 Correct 6497 ms 204260 KB Output is correct
26 Execution timed out 8054 ms 202520 KB Time limit exceeded
27 Halted 0 ms 0 KB -