oj.uz

Submission #906221

# Submission time Handle Problem Language Result Execution time Memory
906221 2024-01-13T19:15:52 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 3500 ms 987056 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 = 1050000;
 
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 dfn[MAX], T, 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) {
		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 < 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 dfn[i] < dfn[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 1669 ms 567800 KB Output is correct
2 Correct 1654 ms 571524 KB Output is correct
3 Correct 1575 ms 524648 KB Output is correct
4 Correct 1544 ms 524676 KB Output is correct
5 Correct 1596 ms 526580 KB Output is correct
6 Correct 1777 ms 533372 KB Output is correct
7 Correct 1695 ms 534112 KB Output is correct
8 Correct 1652 ms 528888 KB Output is correct
9 Correct 1568 ms 523452 KB Output is correct
10 Correct 1608 ms 526604 KB Output is correct
11 Correct 1504 ms 520216 KB Output is correct
12 Correct 1561 ms 524004 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1799 ms 571912 KB Output is correct
2 Correct 1679 ms 568952 KB Output is correct
3 Correct 1588 ms 523308 KB Output is correct
4 Correct 1628 ms 526648 KB Output is correct
5 Correct 1594 ms 526436 KB Output is correct
6 Correct 1695 ms 530252 KB Output is correct
7 Correct 1756 ms 534668 KB Output is correct
8 Correct 1784 ms 534204 KB Output is correct
9 Correct 1750 ms 536512 KB Output is correct
10 Correct 1664 ms 535840 KB Output is correct
11 Correct 1630 ms 531988 KB Output is correct
12 Correct 1710 ms 533476 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1452 ms 560948 KB Output is correct
2 Correct 1412 ms 559376 KB Output is correct
3 Correct 1274 ms 515700 KB Output is correct
4 Correct 1272 ms 514536 KB Output is correct
5 Correct 1217 ms 513336 KB Output is correct
6 Correct 1326 ms 523144 KB Output is correct
7 Correct 1379 ms 522016 KB Output is correct
8 Correct 1360 ms 519636 KB Output is correct
9 Correct 1369 ms 523380 KB Output is correct
10 Correct 1283 ms 523988 KB Output is correct
11 Correct 1275 ms 521204 KB Output is correct
12 Correct 1273 ms 522304 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3234 ms 975372 KB Output is correct
2 Correct 3253 ms 976808 KB Output is correct
3 Runtime error 2702 ms 883448 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 3528 ms 987056 KB Time limit exceeded
2 Halted 0 ms 0 KB -