oj.uz

Submission #1031816

# Submission time Handle Problem Language Result Execution time Memory
1031816 2024-07-23T07:39:11 Z juicy Factories (JOI14_factories) C++17
100 / 100
 1178 ms 211916 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], spt[LG][2 * mxN], lg[2 * mxN], tout[mxN];
long long dep[mxN], dp[mxN][2];
bool vs[mxN];
vector<pair<int, int>> g[mxN];
vector<int> graph[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;
		}
	}
	tout[u] = timer;
}
 
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 Init(int N, int *A, int *B, int *D) {
	for (int i = 0; i < N - 1; ++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 i = 2; i <= timer; ++i) {
		lg[i] = lg[i / 2] + 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)]);
		}
	}
  for (int i = 1; i <= N; ++i) {
    for (int j = 0; j < 2; ++j) {
      dp[i][j] = inf;
    }
  }
}
 
long long Query(int S, int *X, int T, int *Y) {
	vector<int> ver;
	auto add = [&](int u) {
		if (!vs[u]) {
			ver.push_back(u);
			vs[u] = 1;
		}
	};
	for (int i = 0; i < T; ++i) {
		add(++Y[i]);
		dp[Y[i]][0] = dep[Y[i]];
	}
	for (int i = 0; i < S; ++i) {
		add(++X[i]);
		dp[X[i]][1] = dep[X[i]];
	}
	sort(ver.begin(), ver.end(), [&](int i, int j) {
		return ord[i] < ord[j];
	});
	int m = ver.size();
	for (int i = 1; i < m; ++i) {
		add(lca(ver[i], ver[i - 1]));
	}
	sort(ver.begin(), ver.end(), [&](int i, int j) {
		return ord[i] < ord[j];
	});
	vector<int> st;
	for (int u : ver) {
		while (st.size() && tout[st.back()] < ord[u]) {
			st.pop_back();
		}
		if (st.size()) {
			int p = st.back();
			graph[p].push_back(u);
		}
		st.push_back(u);
	}
	long long ans = inf;
	for (int i = ver.size() - 1; ~i; --i) {
		int u = ver[i];
		for (int v : graph[u]) {
			for (int j = 0; j < 2; ++j) {
				dp[u][j] = min(dp[u][j], dp[v][j]);
			}
		}
		ans = min(ans, dp[u][0] + dp[u][1] - 2 * dep[u]);
	}
	for (int u : ver) {
		vs[u] = 0;
    graph[u].clear();
    for (int j = 0; j < 2; ++j) {
      dp[u][j] = inf;
    }
	}
	return ans;
}

Compilation message

factories.cpp: In function 'void Init(int, int*, int*, int*)':
factories.cpp:63:59: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |    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 17 ms 24412 KB Output is correct
2 Correct 429 ms 42344 KB Output is correct
3 Correct 422 ms 42352 KB Output is correct
4 Correct 426 ms 42580 KB Output is correct
5 Correct 383 ms 42648 KB Output is correct
6 Correct 345 ms 42324 KB Output is correct
7 Correct 433 ms 42380 KB Output is correct
8 Correct 418 ms 42756 KB Output is correct
9 Correct 347 ms 42836 KB Output is correct
10 Correct 378 ms 42428 KB Output is correct
11 Correct 429 ms 42388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 24156 KB Output is correct
2 Correct 665 ms 168196 KB Output is correct
3 Correct 747 ms 170388 KB Output is correct
4 Correct 497 ms 168628 KB Output is correct
5 Correct 955 ms 205084 KB Output is correct
6 Correct 721 ms 172628 KB Output is correct
7 Correct 527 ms 69972 KB Output is correct
8 Correct 318 ms 70368 KB Output is correct
9 Correct 353 ms 76404 KB Output is correct
10 Correct 550 ms 71504 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 24412 KB Output is correct
2 Correct 429 ms 42344 KB Output is correct
3 Correct 422 ms 42352 KB Output is correct
4 Correct 426 ms 42580 KB Output is correct
5 Correct 383 ms 42648 KB Output is correct
6 Correct 345 ms 42324 KB Output is correct
7 Correct 433 ms 42380 KB Output is correct
8 Correct 418 ms 42756 KB Output is correct
9 Correct 347 ms 42836 KB Output is correct
10 Correct 378 ms 42428 KB Output is correct
11 Correct 429 ms 42388 KB Output is correct
12 Correct 10 ms 24156 KB Output is correct
13 Correct 665 ms 168196 KB Output is correct
14 Correct 747 ms 170388 KB Output is correct
15 Correct 497 ms 168628 KB Output is correct
16 Correct 955 ms 205084 KB Output is correct
17 Correct 721 ms 172628 KB Output is correct
18 Correct 527 ms 69972 KB Output is correct
19 Correct 318 ms 70368 KB Output is correct
20 Correct 353 ms 76404 KB Output is correct
21 Correct 550 ms 71504 KB Output is correct
22 Correct 1077 ms 181456 KB Output is correct
23 Correct 1046 ms 182720 KB Output is correct
24 Correct 1178 ms 185872 KB Output is correct
25 Correct 1127 ms 189588 KB Output is correct
26 Correct 1008 ms 180816 KB Output is correct
27 Correct 1175 ms 211916 KB Output is correct
28 Correct 873 ms 180404 KB Output is correct
29 Correct 921 ms 179548 KB Output is correct
30 Correct 1006 ms 178832 KB Output is correct
31 Correct 921 ms 179324 KB Output is correct
32 Correct 532 ms 77648 KB Output is correct
33 Correct 442 ms 72332 KB Output is correct
34 Correct 534 ms 68636 KB Output is correct
35 Correct 513 ms 68436 KB Output is correct
36 Correct 549 ms 69228 KB Output is correct
37 Correct 598 ms 69212 KB Output is correct