oj.uz

Submission #906129

# Submission time Handle Problem Language Result Execution time Memory
906129 2024-01-13T14:26:51 Z MilosMilutinovic Prize (CEOI22_prize) C++14
54 / 100
 3500 ms 412196 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], par[20][MAX];
	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) {
		if (sz(ids) < k) {
			ids.push_back(x);
		}
		dep[x] = dep[px] + 1;
		par[0][x] = px;
		for (int i = 1; i < 20; i++)
			par[i][x] = par[i - 1][par[i - 1][x]];
		for (auto& y : gph[x]) {
			if (y == px) continue;
			dfs(y, x);
		}
	}
	int getlca(int s, int e) {
		if (dep[s] < dep[e]) swap(s, e);
		for (int i = 19; i >= 0; i--) 
			if (dep[par[i][s]] >= dep[e])
				s = par[i][s];
		if (s == e) return s;
		for (int i = 19; i >= 0; i--)
			if (par[i][s] != par[i][e])
				s = par[i][s], e = par[i][e];
		return par[0][s];
	}
	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 = 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], par[20][MAX];
	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;
		par[0][x] = px;
		for (int i = 1; i < 20; i++) 
			par[i][x] = par[i - 1][par[i - 1][x]];
		for (auto& y : gph[x]) {
			if (y == px) continue;
			dfs(y, x);
		}
	}
	int getlca(int s, int e) {
		if (dep[s] < dep[e]) swap(s, e);
		for (int i = 19; i >= 0; i--)
			if (dep[par[i][s]] >= dep[e])
				s = par[i][s];
		if (s == e) return s;
		for (int i = 19; i >= 0; i--)
			if (par[i][s] != par[i][e])
				s = par[i][s], e = par[i][e];
		return par[0][s];
	}
	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 = 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 3123 ms 354844 KB Output is correct
2 Correct 3433 ms 358896 KB Output is correct
3 Correct 2480 ms 334932 KB Output is correct
4 Correct 2625 ms 334648 KB Output is correct
5 Correct 2629 ms 337080 KB Output is correct
6 Correct 3316 ms 339084 KB Output is correct
7 Correct 3175 ms 339068 KB Output is correct
8 Correct 3223 ms 336892 KB Output is correct
9 Correct 2549 ms 334916 KB Output is correct
10 Correct 2711 ms 336424 KB Output is correct
11 Correct 2433 ms 330288 KB Output is correct
12 Correct 2554 ms 334304 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3453 ms 359260 KB Output is correct
2 Correct 3157 ms 355276 KB Output is correct
3 Correct 2810 ms 334816 KB Output is correct
4 Correct 2826 ms 337172 KB Output is correct
5 Correct 2644 ms 335852 KB Output is correct
6 Correct 3228 ms 336988 KB Output is correct
7 Correct 3495 ms 340016 KB Output is correct
8 Correct 3450 ms 340660 KB Output is correct
9 Correct 3171 ms 340676 KB Output is correct
10 Correct 3237 ms 340408 KB Output is correct
11 Correct 3135 ms 338260 KB Output is correct
12 Correct 3270 ms 339644 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1570 ms 347244 KB Output is correct
2 Correct 1430 ms 345252 KB Output is correct
3 Correct 1136 ms 323448 KB Output is correct
4 Correct 1106 ms 324988 KB Output is correct
5 Correct 1079 ms 324976 KB Output is correct
6 Correct 1494 ms 328740 KB Output is correct
7 Correct 1430 ms 327024 KB Output is correct
8 Correct 1398 ms 327068 KB Output is correct
9 Correct 1336 ms 327440 KB Output is correct
10 Correct 1351 ms 328884 KB Output is correct
11 Correct 1346 ms 325560 KB Output is correct
12 Correct 1257 ms 328796 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3529 ms 412196 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 3517 ms 399864 KB Time limit exceeded
2 Halted 0 ms 0 KB -