oj.uz

Submission #906135

# Submission time Handle Problem Language Result Execution time Memory
906135 2024-01-13T14:32:45 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 2609 ms 1048576 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 = 2050000;
 
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[MAX], p[MAX];
	pair<int, int> st[MAX][20];
	vector<int> gph[MAX];
	vector<pi> adj[MAX];
	vector<pair<int, int>> euler;
	lint 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[p[s]][k], st[p[e] - (1 << k) + 1][k]).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 < MAX; i++) 
			logs[i] = logs[i >> 1] + 1;
		for (int i = 0; i < sz(euler); i++)
			st[i][0] = euler[i];
		for (int j = 1; j < 20; j++)
			for (int i = 0; i + (1 << j) <= sz(euler); i++)
				st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 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);
	}
	lint query(int x, int y) {
		return dist[x] + dist[y] - 2 * dist[getlca(x, y)];
	}
};
 
namespace tree2 {
	int dfn[MAX], T, dep[MAX], p[MAX], logs[MAX];
	vector<pair<int, int>> euler;
	pair<int, int> st[MAX][20];
	vector<int> gph[MAX];
	vector<pi> adj[MAX];
	lint 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) {
		dfn[x] = ++T;
		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[p[s]][k], st[p[e] - (1 << k) + 1][k]).second;
	}
	void order() {
		sort(all(ids), [&](int i, int j) { return dfn[i] < dfn[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 < MAX; i++) 
			logs[i] = logs[i >> 1] + 1;
		for (int i = 0; i < sz(euler); i++)
			st[i][0] = euler[i];
		for (int j = 1; j < 20; j++)
			for (int i = 0; i + (1 << j) <= sz(euler); i++)
				st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 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 dfn[i] < dfn[j]; });
		for (int x : ord) if (!seen[x]) dfs(x);
	}
	lint 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 1930 ms 659256 KB Output is correct
2 Correct 1817 ms 664700 KB Output is correct
3 Correct 1730 ms 619224 KB Output is correct
4 Correct 1763 ms 618992 KB Output is correct
5 Correct 1844 ms 621556 KB Output is correct
6 Correct 2109 ms 624316 KB Output is correct
7 Correct 1942 ms 628636 KB Output is correct
8 Correct 1919 ms 623188 KB Output is correct
9 Correct 1816 ms 618692 KB Output is correct
10 Correct 1882 ms 621928 KB Output is correct
11 Correct 1886 ms 614384 KB Output is correct
12 Correct 2044 ms 619480 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2045 ms 665132 KB Output is correct
2 Correct 1897 ms 662748 KB Output is correct
3 Correct 2091 ms 619576 KB Output is correct
4 Correct 1793 ms 622556 KB Output is correct
5 Correct 1696 ms 620432 KB Output is correct
6 Correct 1874 ms 625528 KB Output is correct
7 Correct 1853 ms 630112 KB Output is correct
8 Correct 2009 ms 629032 KB Output is correct
9 Correct 1847 ms 630360 KB Output is correct
10 Correct 1916 ms 632048 KB Output is correct
11 Correct 1835 ms 626676 KB Output is correct
12 Correct 1777 ms 630640 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1547 ms 656400 KB Output is correct
2 Correct 1575 ms 655868 KB Output is correct
3 Correct 1340 ms 608596 KB Output is correct
4 Correct 1390 ms 608752 KB Output is correct
5 Correct 1337 ms 608356 KB Output is correct
6 Correct 1413 ms 618776 KB Output is correct
7 Correct 1513 ms 616616 KB Output is correct
8 Correct 1483 ms 615648 KB Output is correct
9 Correct 1356 ms 617768 KB Output is correct
10 Correct 1411 ms 619860 KB Output is correct
11 Correct 1431 ms 615660 KB Output is correct
12 Correct 1436 ms 615020 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2537 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 2609 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -