oj.uz

Submission #1031787

# Submission time Handle Problem Language Result Execution time Memory
1031787 2024-07-23T07:11:52 Z juicy Factories (JOI14_factories) C++17
15 / 100
 8000 ms 150608 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int mxN = 5e5 + 5, LG = 20;
const long long inf = 1e18;

int ord[mxN], sz[mxN], pr[mxN], spt[LG][2 * mxN];
long long dep[mxN], mn[mxN];
bool del[mxN];
vector<pair<int, int>> g[mxN];

int timer = 0;

void pre_dfs(int u) {
	spt[0][ord[u] = ++timer] = u;
	for (auto [v, w] : g[u]) {
		if (!ord[v]) {
			dep[v] = dep[u] + w;
			pre_dfs(v);
			spt[0][++timer] = u;
		}
	}
}

int mint(int u, int v) {
	return ord[u] < ord[v] ? u : v;
}

int lca(int u, int v) {
	int l = ord[u], r = ord[v];
	if (l > r) {
		swap(l, r);
	}
	int k = __lg(r - l + 1);
	return mint(spt[k][l], spt[k][r - (1 << k) + 1]);
}

long long dis(int u, int v) {
	return dep[u] + dep[v] - 2 * dep[lca(u, v)];
}

void dfs(int u, int p) {
	sz[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p) {
			dfs(v, u);
			sz[u] += sz[v];
		}
	}
}

int findCen(int u, int p, int tot) {
	for (auto [v, w] : g[u]) {
		if (!del[v] && v != p && sz[v] * 2 > tot) {
			return findCen(v, u, tot);
		}
	}
	return u;
}

int split(int u) {
	dfs(u, u);
	u = findCen(u, u, sz[u]);
  del[u] = 1;
	for (auto [v, w] : g[u]) {
		if (!del[v]) {
			pr[split(v)] = u;
		}
	}
  return u;
}

void ins(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = min(mn[p], dis(u, p));
	}
}

void ers(int u) {
	for (int p = u; p; p = pr[p]) {
		mn[p] = inf;
	}
}

long long get(int u) {
	long long ans = inf;
	for (int p = u; p; p = pr[p]) {
		ans = min(ans, mn[p] + dis(p, u));
	}
	return ans;
}

void Init(int N, int *A, int *B, int *D) {
	for (int i = 0; i < N; ++i) {
    ++A[i], ++B[i];
		g[A[i]].push_back({B[i], D[i]});
		g[B[i]].push_back({A[i], D[i]});
	}
	pre_dfs(1);
	for (int j = 1; j < LG; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
			spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
		}
	}
  split(1);
  fill(mn + 1, mn + N + 1, inf);
}

long long Query(int S, int *X, int T, int *Y) {
	for (int i = 0; i < T; ++i) {
		ins(++Y[i]);
	}
	long long res = inf;
  for (int i = 0; i < S; ++i) {
    res = min(res, get(++X[i]));
  }
	for (int i = 0; i < T; ++i) {
		ers(Y[i]);
	}
	return res;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:109:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  109 |    spt[j][i] = mint(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                         ~~^~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12632 KB Output is correct
2 Correct 301 ms 30548 KB Output is correct
3 Correct 397 ms 30620 KB Output is correct
4 Correct 367 ms 30436 KB Output is correct
5 Correct 521 ms 30876 KB Output is correct
6 Correct 165 ms 30548 KB Output is correct
7 Correct 336 ms 30436 KB Output is correct
8 Correct 398 ms 30600 KB Output is correct
9 Correct 485 ms 30780 KB Output is correct
10 Correct 169 ms 30544 KB Output is correct
11 Correct 369 ms 30548 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12380 KB Output is correct
2 Correct 1282 ms 150608 KB Output is correct
3 Execution timed out 8026 ms 145240 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 12632 KB Output is correct
2 Correct 301 ms 30548 KB Output is correct
3 Correct 397 ms 30620 KB Output is correct
4 Correct 367 ms 30436 KB Output is correct
5 Correct 521 ms 30876 KB Output is correct
6 Correct 165 ms 30548 KB Output is correct
7 Correct 336 ms 30436 KB Output is correct
8 Correct 398 ms 30600 KB Output is correct
9 Correct 485 ms 30780 KB Output is correct
10 Correct 169 ms 30544 KB Output is correct
11 Correct 369 ms 30548 KB Output is correct
12 Correct 6 ms 12380 KB Output is correct
13 Correct 1282 ms 150608 KB Output is correct
14 Execution timed out 8026 ms 145240 KB Time limit exceeded
15 Halted 0 ms 0 KB -