oj.uz

Submission #906212

# Submission time Handle Problem Language Result Execution time Memory
906212 2024-01-13T16:58:31 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 2706 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 = 4050000;
 
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 1797 ms 872996 KB Output is correct
2 Correct 1868 ms 876552 KB Output is correct
3 Correct 1747 ms 830660 KB Output is correct
4 Correct 1719 ms 830180 KB Output is correct
5 Correct 1830 ms 835012 KB Output is correct
6 Correct 1900 ms 842348 KB Output is correct
7 Correct 1818 ms 839376 KB Output is correct
8 Correct 1883 ms 835528 KB Output is correct
9 Correct 1739 ms 830152 KB Output is correct
10 Correct 1734 ms 834504 KB Output is correct
11 Correct 1607 ms 826920 KB Output is correct
12 Correct 1763 ms 830872 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1950 ms 880656 KB Output is correct
2 Correct 1785 ms 873900 KB Output is correct
3 Correct 1807 ms 830140 KB Output is correct
4 Correct 1837 ms 835164 KB Output is correct
5 Correct 1837 ms 832008 KB Output is correct
6 Correct 1925 ms 835696 KB Output is correct
7 Correct 2005 ms 841880 KB Output is correct
8 Correct 1898 ms 840700 KB Output is correct
9 Correct 1950 ms 842616 KB Output is correct
10 Correct 2005 ms 843864 KB Output is correct
11 Correct 1912 ms 836920 KB Output is correct
12 Correct 1952 ms 841988 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1662 ms 864820 KB Output is correct
2 Correct 1659 ms 864628 KB Output is correct
3 Correct 1436 ms 820144 KB Output is correct
4 Correct 1447 ms 819608 KB Output is correct
5 Correct 1375 ms 818212 KB Output is correct
6 Correct 1467 ms 826536 KB Output is correct
7 Correct 1498 ms 826256 KB Output is correct
8 Correct 1494 ms 825572 KB Output is correct
9 Correct 1465 ms 827592 KB Output is correct
10 Correct 1529 ms 827324 KB Output is correct
11 Correct 1521 ms 826516 KB Output is correct
12 Correct 1525 ms 826824 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 2553 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 2706 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -