oj.uz

Submission #906228

# Submission time Handle Problem Language Result Execution time Memory
906228 2024-01-13T19:30:37 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 3500 ms 1008548 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[2 * MAX][21];
	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[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 < 2 * 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 < 21; 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);
	}
	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[2 * MAX][21];
	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[p[s]][k], st[p[e] - (1 << k) + 1][k]).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[i][0] = euler[i];
		for (int j = 1; j < 21; 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 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 1640 ms 578348 KB Output is correct
2 Correct 1692 ms 585300 KB Output is correct
3 Correct 1650 ms 537776 KB Output is correct
4 Correct 1561 ms 537136 KB Output is correct
5 Correct 1564 ms 539872 KB Output is correct
6 Correct 1721 ms 546116 KB Output is correct
7 Correct 1730 ms 547028 KB Output is correct
8 Correct 1683 ms 541360 KB Output is correct
9 Correct 1535 ms 536128 KB Output is correct
10 Correct 1642 ms 539748 KB Output is correct
11 Correct 1545 ms 528360 KB Output is correct
12 Correct 1628 ms 534792 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1747 ms 585168 KB Output is correct
2 Correct 1700 ms 579600 KB Output is correct
3 Correct 1634 ms 536024 KB Output is correct
4 Correct 1642 ms 539836 KB Output is correct
5 Correct 1623 ms 539024 KB Output is correct
6 Correct 1696 ms 541404 KB Output is correct
7 Correct 1756 ms 547124 KB Output is correct
8 Correct 1781 ms 548028 KB Output is correct
9 Correct 1699 ms 548676 KB Output is correct
10 Correct 1805 ms 548640 KB Output is correct
11 Correct 1709 ms 544448 KB Output is correct
12 Correct 1745 ms 546656 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1480 ms 570648 KB Output is correct
2 Correct 1549 ms 568832 KB Output is correct
3 Correct 1241 ms 523240 KB Output is correct
4 Correct 1283 ms 523104 KB Output is correct
5 Correct 1278 ms 523060 KB Output is correct
6 Correct 1422 ms 533152 KB Output is correct
7 Correct 1387 ms 531204 KB Output is correct
8 Correct 1420 ms 527516 KB Output is correct
9 Correct 1370 ms 531628 KB Output is correct
10 Correct 1334 ms 533524 KB Output is correct
11 Correct 1360 ms 529864 KB Output is correct
12 Correct 1337 ms 529812 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3510 ms 992280 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3532 ms 1008548 KB Time limit exceeded
2 Halted 0 ms 0 KB -