oj.uz

Submission #906126

# Submission time Handle Problem Language Result Execution time Memory
906126 2024-01-13T14:24:34 Z MilosMilutinovic Prize (CEOI22_prize) C++17
19 / 100
 3500 ms 397356 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;
 
struct 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)];
	}
} tree1;
 
struct 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)];
	}
} tree2;
 
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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3359 ms 346900 KB Output is correct
2 Execution timed out 3525 ms 351468 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

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

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1619 ms 342140 KB Output is correct
2 Correct 1651 ms 338808 KB Output is correct
3 Correct 1231 ms 325784 KB Output is correct
4 Correct 1249 ms 325620 KB Output is correct
5 Correct 1107 ms 325712 KB Output is correct
6 Correct 1493 ms 329540 KB Output is correct
7 Correct 1432 ms 327488 KB Output is correct
8 Correct 1427 ms 318512 KB Output is correct
9 Correct 1356 ms 329952 KB Output is correct
10 Correct 1280 ms 328684 KB Output is correct
11 Correct 1253 ms 328116 KB Output is correct
12 Correct 1407 ms 327916 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3562 ms 397356 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 3539 ms 385056 KB Time limit exceeded
2 Halted 0 ms 0 KB -