oj.uz

Submission #681218

# Submission time Handle Problem Language Result Execution time Memory
681218 2023-01-12T14:37:46 Z SanguineChameleon Factories (JOI14_factories) C++17
100 / 100
 3181 ms 175280 KB 
#include "factories.h"

#include <bits/stdc++.h>
using namespace std;

const int ms = 5e5 + 20;
const long long inf = 1e18L + 20;
const int st = 20;
vector<pair<int, int>> adj[ms];
vector<pair<int, long long>> vch[ms];
long long de[ms];
int ti[ms];
int to[ms];
int f[ms];
long long dp[ms][2];
int par[ms][st];
int tz;

void dfs1(int u, int pr) {
	ti[u] = ++tz;
	for (auto x: adj[u]) {
		int v = x.first;
		int w = x.second;
		if (v != pr) {
			par[v][0] = u;
			de[v] = de[u] + w;
			dfs1(v, u);
		}
	}
	to[u] = ++tz;
}

bool cmp(int u, int v) {
	return ti[u] < ti[v];
}

bool anc(int u, int v) {
	return ti[u] < ti[v] && to[v] < to[u];
}

int lca(int u, int v) {
	if (anc(u, v)) {
		return u;
	}
	if (anc(v, u)) {
		return v;
	}
	for (int i = st - 1; i >= 0; i--) {
		if (!anc(par[u][i], v)) {
			u = par[u][i];
		}
	}
	return par[u][0];
}

void Init(int N, int A[], int B[], int D[]) {
	for (int i = 0; i < N - 1; i++) {
		int u = A[i];
		int v = B[i];
		u++;
		v++;
		int w = D[i];
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}
	for (int i = 1; i <= N; i++) {
		f[i] = -1;
	}
	par[1][0] = 1;
	dfs1(1, -1);
	for (int k = 1; k < st; k++) {
		for (int i = 1; i <= N; i++) {
			par[i][k] = par[par[i][k - 1]][k - 1];
		}
	}
}

void dfs2(int u) {
	dp[u][0] = inf;
	dp[u][1] = inf;
	if (f[u] != -1) {
		dp[u][f[u]] = 0;
	}
	for (auto x: vch[u]) {
		int v = x.first;
		long long w = x.second;
		dfs2(v);
		dp[u][0] = min(dp[u][0], dp[v][0] + w);
		dp[u][1] = min(dp[u][1], dp[v][1] + w);
	}
}

long long Query(int S, int X[], int T, int Y[]) {
	vector<int> q;
	for (int i = 0; i < S; i++) {
		int u = X[i];
		u++;
		f[u] = 0;
		q.push_back(u);
	}
	for (int i = 0; i < T; i++) {
		int u = Y[i];
		u++;
		f[u] = 1;
		q.push_back(u);
	}
	int sz = q.size();
	sort(q.begin(), q.end(), cmp);
	for (int i = 0; i < sz - 1; i++) {
		q.push_back(lca(q[i], q[i + 1]));
	}
	sort(q.begin(), q.end(), cmp);
	q.erase(unique(q.begin(), q.end()), q.end());
	sz = q.size();
	int root = q[0];
	vector<int> p = {root};
	for (int i = 1; i < sz; i++) {
		int v = q[i];
		while (!anc(p.back(), v)) {
			p.pop_back();
		}
		int u = p.back();
		vch[u].push_back({v, de[v] - de[u]});
		p.push_back(v);
	}
	dfs2(root);
	long long res = inf;
	for (auto u: q) {
		res = min(res, dp[u][0] + dp[u][1]);
		vch[u].clear();
		f[u] = -1;
	}
	return res;
}

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24276 KB Output is correct
2 Correct 924 ms 42200 KB Output is correct
3 Correct 849 ms 42292 KB Output is correct
4 Correct 946 ms 42284 KB Output is correct
5 Correct 718 ms 42632 KB Output is correct
6 Correct 678 ms 42296 KB Output is correct
7 Correct 846 ms 42332 KB Output is correct
8 Correct 873 ms 42456 KB Output is correct
9 Correct 744 ms 42636 KB Output is correct
10 Correct 663 ms 42160 KB Output is correct
11 Correct 866 ms 42232 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 24020 KB Output is correct
2 Correct 1330 ms 130824 KB Output is correct
3 Correct 1922 ms 133564 KB Output is correct
4 Correct 960 ms 131188 KB Output is correct
5 Correct 1298 ms 167452 KB Output is correct
6 Correct 1937 ms 135492 KB Output is correct
7 Correct 1536 ms 64284 KB Output is correct
8 Correct 929 ms 64432 KB Output is correct
9 Correct 871 ms 70556 KB Output is correct
10 Correct 1556 ms 65788 KB Output is correct

Subtask #3
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 24276 KB Output is correct
2 Correct 924 ms 42200 KB Output is correct
3 Correct 849 ms 42292 KB Output is correct
4 Correct 946 ms 42284 KB Output is correct
5 Correct 718 ms 42632 KB Output is correct
6 Correct 678 ms 42296 KB Output is correct
7 Correct 846 ms 42332 KB Output is correct
8 Correct 873 ms 42456 KB Output is correct
9 Correct 744 ms 42636 KB Output is correct
10 Correct 663 ms 42160 KB Output is correct
11 Correct 866 ms 42232 KB Output is correct
12 Correct 15 ms 24020 KB Output is correct
13 Correct 1330 ms 130824 KB Output is correct
14 Correct 1922 ms 133564 KB Output is correct
15 Correct 960 ms 131188 KB Output is correct
16 Correct 1298 ms 167452 KB Output is correct
17 Correct 1937 ms 135492 KB Output is correct
18 Correct 1536 ms 64284 KB Output is correct
19 Correct 929 ms 64432 KB Output is correct
20 Correct 871 ms 70556 KB Output is correct
21 Correct 1556 ms 65788 KB Output is correct
22 Correct 2744 ms 147272 KB Output is correct
23 Correct 2364 ms 148404 KB Output is correct
24 Correct 2811 ms 151476 KB Output is correct
25 Correct 2839 ms 153988 KB Output is correct
26 Correct 3181 ms 144432 KB Output is correct
27 Correct 2403 ms 175280 KB Output is correct
28 Correct 1580 ms 146260 KB Output is correct
29 Correct 3087 ms 143228 KB Output is correct
30 Correct 3037 ms 142336 KB Output is correct
31 Correct 2991 ms 142668 KB Output is correct
32 Correct 1321 ms 73388 KB Output is correct
33 Correct 1074 ms 67236 KB Output is correct
34 Correct 1439 ms 63276 KB Output is correct
35 Correct 1419 ms 63232 KB Output is correct
36 Correct 1652 ms 63956 KB Output is correct
37 Correct 1644 ms 63908 KB Output is correct