oj.uz

Submission #890116

# Submission time Handle Problem Language Result Execution time Memory
890116 2023-12-20T14:51:42 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 192804 KB 
#include <bits/stdc++.h>
#include <factories.h>
#pragma  GCC optimize ("Ofast")
using namespace std;
 
const int N = 500002, L = 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 36 ms 37468 KB Output is correct
2 Correct 482 ms 41856 KB Output is correct
3 Correct 952 ms 41864 KB Output is correct
4 Correct 293 ms 41812 KB Output is correct
5 Correct 585 ms 42064 KB Output is correct
6 Correct 713 ms 41856 KB Output is correct
7 Correct 996 ms 41808 KB Output is correct
8 Correct 1123 ms 41868 KB Output is correct
9 Correct 589 ms 42064 KB Output is correct
10 Correct 732 ms 41856 KB Output is correct
11 Correct 954 ms 41872 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37464 KB Output is correct
2 Correct 1093 ms 175440 KB Output is correct
3 Correct 1962 ms 177212 KB Output is correct
4 Correct 736 ms 175932 KB Output is correct
5 Correct 2749 ms 192804 KB Output is correct
6 Correct 1859 ms 177368 KB Output is correct
7 Correct 1768 ms 69264 KB Output is correct
8 Correct 978 ms 69316 KB Output is correct
9 Correct 3058 ms 71196 KB Output is correct
10 Correct 1424 ms 69700 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37468 KB Output is correct
2 Correct 482 ms 41856 KB Output is correct
3 Correct 952 ms 41864 KB Output is correct
4 Correct 293 ms 41812 KB Output is correct
5 Correct 585 ms 42064 KB Output is correct
6 Correct 713 ms 41856 KB Output is correct
7 Correct 996 ms 41808 KB Output is correct
8 Correct 1123 ms 41868 KB Output is correct
9 Correct 589 ms 42064 KB Output is correct
10 Correct 732 ms 41856 KB Output is correct
11 Correct 954 ms 41872 KB Output is correct
12 Correct 7 ms 37464 KB Output is correct
13 Correct 1093 ms 175440 KB Output is correct
14 Correct 1962 ms 177212 KB Output is correct
15 Correct 736 ms 175932 KB Output is correct
16 Correct 2749 ms 192804 KB Output is correct
17 Correct 1859 ms 177368 KB Output is correct
18 Correct 1768 ms 69264 KB Output is correct
19 Correct 978 ms 69316 KB Output is correct
20 Correct 3058 ms 71196 KB Output is correct
21 Correct 1424 ms 69700 KB Output is correct
22 Correct 4189 ms 176704 KB Output is correct
23 Correct 2745 ms 177492 KB Output is correct
24 Correct 6406 ms 177964 KB Output is correct
25 Correct 5939 ms 179672 KB Output is correct
26 Execution timed out 8034 ms 178516 KB Time limit exceeded
27 Halted 0 ms 0 KB -