oj.uz

Submission #340004

# Submission time Handle Problem Language Result Execution time Memory
340004 2020-12-26T15:00:03 Z penguinhacker Factories (JOI14_factories) C++14
100 / 100
 6049 ms 335416 KB 
#include <bits/stdc++.h>
#include "factories.h"
using namespace std;

#define ll long long
#define ar array

const int mxN = 500000;
int n, sz[mxN];
ll best[mxN];
bool dead[mxN];
vector<pair<int, int>> adj[mxN];
vector<pair<int, ll>> par[mxN];

int dfs_sz(int u, int p) {
	sz[u] = 1;
	for (pair<int, int>& v : adj[u]) if (v.first != p && !dead[v.first])
		sz[u] += dfs_sz(v.first, u);
	return sz[u];
}

int get_centroid(int u, int p, int tsz) {
	for (pair<int, int>& v : adj[u]) if (v.first != p && !dead[v.first] && 2 * sz[v.first] > tsz)
		return get_centroid(v.first, u, tsz);
	return u;
}

void dfs(int u, int p, int c, ll d) {
	par[u].emplace_back(c, d);
	for (pair<int, int>& v : adj[u]) if (v.first != p && !dead[v.first])
		dfs(v.first, u, c, d + v.second);
}

void centroid(int u = 0) {
	u = get_centroid(u, -1, dfs_sz(u, -1));
	dfs(u, -1, u, 0);
	dead[u] = 1;
	for (pair<int, int> v : adj[u]) if (!dead[v.first])
		centroid(v.first);
	dead[u] = 0;
}

void Init(int N, int A[], int B[], int D[]) {
	n = N;
	for (int i = 0; i < n - 1; ++i) {
		int a = A[i], b = B[i], d = D[i];
		adj[a].emplace_back(b, d);
		adj[b].emplace_back(a, d);
	}
	centroid();
	fill(best, best + n, 1e18);
}

ll Query(int S, int X[], int T, int Y[]) {
	vector<int> rb; // rollback best array
	for (int i = 0; i < S; ++i) {
		int u = X[i];
		for (pair<int, ll> p : par[u]) {
			best[p.first] = min(best[p.first], p.second);
			rb.push_back(p.first);
		}
	}
	ll ans = 1e18;
	for (int i = 0; i < T; ++i) {
		int u = Y[i];
		for (pair<int, ll> p : par[u])
			ans = min(ans, best[p.first] + p.second);
	}
	for (int i : rb)
		best[i] = 1e18;
	assert(ans < (ll)1e18);
	return ans;
}

/*int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q; cin >> n >> q;
	int a[n - 1], b[n - 1], d[n - 1];
	for (int i = 0; i < n - 1; ++i)
		cin >> a[i] >> b[i] >> d[i];
	Init(n, a, b, d);
	for (int i = 0; i < q; ++i) {
		int s, t; cin >> s >> t;
		int x[s], y[t];
		for (int j = 0; j < s; ++j)
			cin >> x[j];
		for (int j = 0; j < t; ++j)
			cin >> y[j];
		cout << Query(s, x, t, y) << "\n";
	}
	return 0;
}
*/

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 366 ms 33260 KB Output is correct
3 Correct 408 ms 42860 KB Output is correct
4 Correct 412 ms 43204 KB Output is correct
5 Correct 440 ms 43392 KB Output is correct
6 Correct 309 ms 42028 KB Output is correct
7 Correct 411 ms 42920 KB Output is correct
8 Correct 410 ms 42988 KB Output is correct
9 Correct 428 ms 43392 KB Output is correct
10 Correct 313 ms 41964 KB Output is correct
11 Correct 408 ms 42860 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 24044 KB Output is correct
2 Correct 2806 ms 190624 KB Output is correct
3 Correct 4104 ms 262528 KB Output is correct
4 Correct 1091 ms 87764 KB Output is correct
5 Correct 5233 ms 332588 KB Output is correct
6 Correct 4170 ms 260732 KB Output is correct
7 Correct 1305 ms 76268 KB Output is correct
8 Correct 645 ms 54220 KB Output is correct
9 Correct 1464 ms 88532 KB Output is correct
10 Correct 1342 ms 77420 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24300 KB Output is correct
2 Correct 366 ms 33260 KB Output is correct
3 Correct 408 ms 42860 KB Output is correct
4 Correct 412 ms 43204 KB Output is correct
5 Correct 440 ms 43392 KB Output is correct
6 Correct 309 ms 42028 KB Output is correct
7 Correct 411 ms 42920 KB Output is correct
8 Correct 410 ms 42988 KB Output is correct
9 Correct 428 ms 43392 KB Output is correct
10 Correct 313 ms 41964 KB Output is correct
11 Correct 408 ms 42860 KB Output is correct
12 Correct 19 ms 24044 KB Output is correct
13 Correct 2806 ms 190624 KB Output is correct
14 Correct 4104 ms 262528 KB Output is correct
15 Correct 1091 ms 87764 KB Output is correct
16 Correct 5233 ms 332588 KB Output is correct
17 Correct 4170 ms 260732 KB Output is correct
18 Correct 1305 ms 76268 KB Output is correct
19 Correct 645 ms 54220 KB Output is correct
20 Correct 1464 ms 88532 KB Output is correct
21 Correct 1342 ms 77420 KB Output is correct
22 Correct 3106 ms 193300 KB Output is correct
23 Correct 3263 ms 200156 KB Output is correct
24 Correct 4652 ms 267708 KB Output is correct
25 Correct 4716 ms 269588 KB Output is correct
26 Correct 4786 ms 261728 KB Output is correct
27 Correct 6049 ms 335416 KB Output is correct
28 Correct 1378 ms 91512 KB Output is correct
29 Correct 4754 ms 260212 KB Output is correct
30 Correct 4774 ms 260268 KB Output is correct
31 Correct 4678 ms 260516 KB Output is correct
32 Correct 1492 ms 97084 KB Output is correct
33 Correct 663 ms 57540 KB Output is correct
34 Correct 1027 ms 72044 KB Output is correct
35 Correct 1029 ms 72940 KB Output is correct
36 Correct 1282 ms 77676 KB Output is correct
37 Correct 1252 ms 77676 KB Output is correct