oj.uz

Submission #890097

# Submission time Handle Problem Language Result Execution time Memory
890097 2023-12-20T14:13:28 Z Onown Factories (JOI14_factories) C++17
33 / 100
 8000 ms 204368 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:3:42: warning: bad option '-f unroll-loops' to pragma 'optimize' [-Wpragmas]
    3 | #pragma  GCC optimize ("O2, unroll-loops")
      |                                          ^
factories.cpp:13:22: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   13 | void dfs(int v, int p) {
      |                      ^
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())
      |        ~~^~~~~~~~~~~~~~~~
factories.cpp: At global scope:
factories.cpp:31:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   31 | void dfsu(int v, int p) {
      |                       ^
factories.cpp:38:23: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   38 | void dfsd(int v, int p) {
      |                       ^
factories.cpp:45:32: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   45 | long long distance(int v, int u) {
      |                                ^
factories.cpp:64:43: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   64 | void Init(int N, int A[], int B[], int D[]) {
      |                                           ^
factories.cpp:79:47: warning: bad option '-f unroll-loops' to attribute 'optimize' [-Wattributes]
   79 | long long Query(int S, int X[], int T, int Y[]) {
      |                                               ^

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35504 KB Output is correct
2 Correct 495 ms 41848 KB Output is correct
3 Correct 980 ms 41860 KB Output is correct
4 Correct 293 ms 41864 KB Output is correct
5 Correct 594 ms 42128 KB Output is correct
6 Correct 855 ms 41864 KB Output is correct
7 Correct 1012 ms 41876 KB Output is correct
8 Correct 1100 ms 41864 KB Output is correct
9 Correct 589 ms 42020 KB Output is correct
10 Correct 838 ms 41864 KB Output is correct
11 Correct 981 ms 41876 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 35464 KB Output is correct
2 Correct 1289 ms 186936 KB Output is correct
3 Correct 2269 ms 188932 KB Output is correct
4 Correct 855 ms 188060 KB Output is correct
5 Correct 3168 ms 204368 KB Output is correct
6 Correct 1989 ms 189268 KB Output is correct
7 Correct 1986 ms 69256 KB Output is correct
8 Correct 1030 ms 69300 KB Output is correct
9 Correct 2977 ms 71192 KB Output is correct
10 Correct 1471 ms 69720 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 35504 KB Output is correct
2 Correct 495 ms 41848 KB Output is correct
3 Correct 980 ms 41860 KB Output is correct
4 Correct 293 ms 41864 KB Output is correct
5 Correct 594 ms 42128 KB Output is correct
6 Correct 855 ms 41864 KB Output is correct
7 Correct 1012 ms 41876 KB Output is correct
8 Correct 1100 ms 41864 KB Output is correct
9 Correct 589 ms 42020 KB Output is correct
10 Correct 838 ms 41864 KB Output is correct
11 Correct 981 ms 41876 KB Output is correct
12 Correct 7 ms 35464 KB Output is correct
13 Correct 1289 ms 186936 KB Output is correct
14 Correct 2269 ms 188932 KB Output is correct
15 Correct 855 ms 188060 KB Output is correct
16 Correct 3168 ms 204368 KB Output is correct
17 Correct 1989 ms 189268 KB Output is correct
18 Correct 1986 ms 69256 KB Output is correct
19 Correct 1030 ms 69300 KB Output is correct
20 Correct 2977 ms 71192 KB Output is correct
21 Correct 1471 ms 69720 KB Output is correct
22 Correct 4745 ms 188276 KB Output is correct
23 Correct 3104 ms 189232 KB Output is correct
24 Correct 6715 ms 189928 KB Output is correct
25 Correct 6474 ms 191436 KB Output is correct
26 Execution timed out 8018 ms 189980 KB Time limit exceeded
27 Halted 0 ms 0 KB -