oj.uz

Submission #906226

# Submission time Handle Problem Language Result Execution time Memory
906226 2024-01-13T19:27:45 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 3500 ms 972300 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][20];
	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 < 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);
	}
	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][20];
	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 < 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 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 1745 ms 560148 KB Output is correct
2 Correct 1783 ms 563960 KB Output is correct
3 Correct 1598 ms 516312 KB Output is correct
4 Correct 1597 ms 516432 KB Output is correct
5 Correct 1567 ms 518720 KB Output is correct
6 Correct 1749 ms 525168 KB Output is correct
7 Correct 1764 ms 525724 KB Output is correct
8 Correct 1704 ms 522800 KB Output is correct
9 Correct 1620 ms 516124 KB Output is correct
10 Correct 1596 ms 518068 KB Output is correct
11 Correct 1590 ms 514452 KB Output is correct
12 Correct 1590 ms 516432 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1710 ms 564060 KB Output is correct
2 Correct 1754 ms 558128 KB Output is correct
3 Correct 1658 ms 515804 KB Output is correct
4 Correct 1658 ms 518188 KB Output is correct
5 Correct 1553 ms 517488 KB Output is correct
6 Correct 1709 ms 523368 KB Output is correct
7 Correct 1813 ms 526344 KB Output is correct
8 Correct 1722 ms 526436 KB Output is correct
9 Correct 1700 ms 527260 KB Output is correct
10 Correct 1700 ms 526740 KB Output is correct
11 Correct 1642 ms 524412 KB Output is correct
12 Correct 1694 ms 527676 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1389 ms 551612 KB Output is correct
2 Correct 1387 ms 548848 KB Output is correct
3 Correct 1206 ms 505284 KB Output is correct
4 Correct 1195 ms 504312 KB Output is correct
5 Correct 1205 ms 504924 KB Output is correct
6 Correct 1311 ms 513720 KB Output is correct
7 Correct 1327 ms 512620 KB Output is correct
8 Correct 1313 ms 510800 KB Output is correct
9 Correct 1255 ms 512812 KB Output is correct
10 Correct 1328 ms 512888 KB Output is correct
11 Correct 1311 ms 513652 KB Output is correct
12 Correct 1279 ms 513056 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3315 ms 960000 KB Output is correct
2 Correct 3184 ms 959396 KB Output is correct
3 Runtime error 2584 ms 867108 KB Execution killed with signal 13
4 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

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