oj.uz

Submission #906229

# Submission time Handle Problem Language Result Execution time Memory
906229 2024-01-13T19:36:48 Z MilosMilutinovic Prize (CEOI22_prize) C++14
100 / 100
 2980 ms 991044 KB 
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<int, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
const int MAX = 1000010;
 
int n, k, q, t, r1, r2;
int a[MAX], b[MAX], c[MAX], d[MAX];
vector<int> ids;
 
namespace tree1 {
	int dep[MAX], logs[2 * MAX], p[MAX];
	pair<int, int> st[21][2 * MAX];
	vector<int> gph[MAX];
	vector<pi> adj[MAX];
	vector<pair<int, int>> euler;
	int dist[MAX];
	bool seen[MAX];
	void add(int u, int v) {
		gph[u].push_back(v);
		gph[v].push_back(u);
	}
	void dfs(int x, int px) {
		if (sz(ids) < k) {
			ids.push_back(x);
		}
		dep[x] = dep[px] + 1;
		p[x] = sz(euler);
		euler.push_back({dep[x], x});
		for (auto& y : gph[x]) {
			if (y == px) continue;
			dfs(y, x);
			euler.push_back({dep[x], x});
		}
	}
	int getlca(int s, int e) {
		if (p[s] > p[e]) swap(s, e);
		int k = logs[p[e] - p[s] + 1];
		return min(st[k][p[s]], st[k][p[e] - (1 << k) + 1]).second;
	}
	void dfs(int x) {
		seen[x] = true;
		for (auto& y : adj[x]) {
			if (seen[y[0]]) continue;
			dist[y[0]] = dist[x] + y[1];
			dfs(y[0]);
		}
	}
	void build() {
		for (int i = 2; i < 2 * MAX; i++) 
			logs[i] = logs[i >> 1] + 1;
		for (int i = 0; i < sz(euler); i++)
			st[0][i] = euler[i];
		for (int j = 1; j < 21; j++)
			for (int i = 0; i + (1 << j) <= sz(euler); i++)
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		for (int i = 0; i + 1 < k; i++) {
			int x = ids[i];
			int y = ids[i + 1];
			int z = getlca(ids[i], ids[i + 1]);
			adj[x].push_back({z, -a[i]});
			adj[z].push_back({x, a[i]});
			adj[y].push_back({z, -b[i]});
			adj[z].push_back({y, b[i]});
		}
		dfs(r1);
	}
	int query(int x, int y) {
		return dist[x] + dist[y] - 2 * dist[getlca(x, y)];
	}
};
 
namespace tree2 {
	int dep[MAX], p[MAX], logs[2 * MAX];
	vector<pair<int, int>> euler;
	pair<int, int> st[21][2 * MAX];
	vector<int> gph[MAX];
	vector<pi> adj[MAX];
	int dist[MAX];
	bool seen[MAX];
	void add(int u, int v) {
		gph[u].push_back(v);
		gph[v].push_back(u);
	}
	void dfs(int x, int px) {
		dep[x] = dep[px] + 1;
		p[x] = sz(euler);
		euler.push_back({dep[x], x});
		for (auto& y : gph[x]) {
			if (y == px) continue;
			dfs(y, x);
			euler.push_back({dep[x], x});
		}
	}
	int getlca(int s, int e) {
		if (p[s] > p[e]) swap(s, e);
		int k = logs[p[e] - p[s] + 1];
		return min(st[k][p[s]], st[k][p[e] - (1 << k) + 1]).second;
	}
	void order() {
		sort(all(ids), [&](int i, int j) { return p[i] < p[j]; });
	}
	void dfs(int x) {
		seen[x] = true;
		for (auto& y : adj[x]) {
			if (seen[y[0]]) continue;
			dist[y[0]] = dist[x] + y[1];
			dfs(y[0]);
		}
	}
	void build() {
		for (int i = 2; i < 2 * MAX; i++) 
			logs[i] = logs[i >> 1] + 1;
		for (int i = 0; i < sz(euler); i++)
			st[0][i] = euler[i];
		for (int j = 1; j < 21; j++)
			for (int i = 0; i + (1 << j) <= sz(euler); i++)
				st[j][i] = min(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
		for (int i = 0; i + 1 < k; i++) {
			int x = ids[i];
			int y = ids[i + 1];
			int z = getlca(ids[i], ids[i + 1]);
			adj[x].push_back({z, -c[i]});
			adj[z].push_back({x, c[i]});
			adj[y].push_back({z, -d[i]});
			adj[z].push_back({y, d[i]});
		}
		vector<int> ord(n);
		iota(all(ord), 0);
		sort(all(ord), [&](int i, int j) { return p[i] < p[j]; });
		for (int x : ord) if (!seen[x]) dfs(x);
	}
	int query(int x, int y) {
		return dist[x] + dist[y] - 2 * dist[getlca(x, y)];
	}
};
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> k >> q >> t;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		if (p == -1) {
			r1 = i;
		} else {
			--p;
			tree1::add(i, p);
		}
	}
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		if (p == -1) {
			r2 = i;
		} else {
			--p;
			tree2::add(i, p);
		}
	}
	tree1::dfs(r1, r1);
	tree2::dfs(r2, r2);
	tree2::order();
	for (int i = 0; i < k; i++) {
		cout << ids[i] + 1 << " ";
	}
	cout << "\n";
	for (int i = 0; i + 1 < k; i++) {
		cout << "? " << ids[i] + 1 << " " << ids[i + 1] + 1 << "\n";
	}
	cout << "!" << endl;
	for (int i = 0; i + 1 < k; i++) {
		cin >> a[i] >> b[i] >> c[i] >> d[i];
	}
	tree1::build();
	tree2::build();
	vector<int> x(t), y(t);
	for (int i = 0; i < t; i++) {
		cin >> x[i] >> y[i];
		--x[i]; --y[i];
	}
	for (int i = 0; i < t; i++) {
		cout << tree1::query(x[i], y[i]) << " " << tree2::query(x[i], y[i]) << "\n";
	}
	cout << endl;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1306 ms 625732 KB Output is correct
2 Correct 1328 ms 632536 KB Output is correct
3 Correct 1233 ms 584976 KB Output is correct
4 Correct 1211 ms 584456 KB Output is correct
5 Correct 1308 ms 587040 KB Output is correct
6 Correct 1371 ms 593332 KB Output is correct
7 Correct 1362 ms 593368 KB Output is correct
8 Correct 1356 ms 589460 KB Output is correct
9 Correct 1231 ms 583632 KB Output is correct
10 Correct 1235 ms 586720 KB Output is correct
11 Correct 1162 ms 576640 KB Output is correct
12 Correct 1194 ms 582124 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1415 ms 632380 KB Output is correct
2 Correct 1382 ms 626576 KB Output is correct
3 Correct 1249 ms 582496 KB Output is correct
4 Correct 1350 ms 587452 KB Output is correct
5 Correct 1266 ms 587284 KB Output is correct
6 Correct 1364 ms 588380 KB Output is correct
7 Correct 1475 ms 594364 KB Output is correct
8 Correct 1443 ms 594724 KB Output is correct
9 Correct 1404 ms 596000 KB Output is correct
10 Correct 1474 ms 594860 KB Output is correct
11 Correct 1292 ms 591592 KB Output is correct
12 Correct 1420 ms 593644 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 618324 KB Output is correct
2 Correct 1156 ms 616504 KB Output is correct
3 Correct 965 ms 571228 KB Output is correct
4 Correct 917 ms 570856 KB Output is correct
5 Correct 882 ms 570412 KB Output is correct
6 Correct 1028 ms 579812 KB Output is correct
7 Correct 1076 ms 578272 KB Output is correct
8 Correct 972 ms 575292 KB Output is correct
9 Correct 958 ms 579552 KB Output is correct
10 Correct 985 ms 581352 KB Output is correct
11 Correct 985 ms 577024 KB Output is correct
12 Correct 987 ms 577132 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2544 ms 976356 KB Output is correct
2 Correct 2469 ms 977052 KB Output is correct
3 Correct 2084 ms 883800 KB Output is correct
4 Correct 2165 ms 884784 KB Output is correct
5 Correct 2107 ms 885376 KB Output is correct
6 Correct 2321 ms 900532 KB Output is correct
7 Correct 2336 ms 899776 KB Output is correct
8 Correct 2264 ms 900160 KB Output is correct
9 Correct 2186 ms 900708 KB Output is correct
10 Correct 2262 ms 900196 KB Output is correct
11 Correct 2136 ms 900952 KB Output is correct
12 Correct 2173 ms 900616 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2716 ms 991044 KB Output is correct
2 Correct 2769 ms 990944 KB Output is correct
3 Correct 2588 ms 900884 KB Output is correct
4 Correct 2670 ms 902596 KB Output is correct
5 Correct 2564 ms 900728 KB Output is correct
6 Correct 2980 ms 918028 KB Output is correct
7 Correct 2817 ms 916744 KB Output is correct
8 Correct 2891 ms 918008 KB Output is correct
9 Correct 2753 ms 919168 KB Output is correct
10 Correct 2797 ms 918836 KB Output is correct
11 Correct 2675 ms 919460 KB Output is correct
12 Correct 2738 ms 919556 KB Output is correct