oj.uz

Submission #906121

# Submission time Handle Problem Language Result Execution time Memory
906121 2024-01-13T14:20:38 Z MilosMilutinovic Prize (CEOI22_prize) C++14
29 / 100
 3500 ms 397468 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 << endl;
	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 3257 ms 347136 KB Output is correct
2 Correct 3320 ms 351796 KB Output is correct
3 Correct 2576 ms 335296 KB Output is correct
4 Correct 2519 ms 334612 KB Output is correct
5 Correct 2641 ms 337252 KB Output is correct
6 Correct 3251 ms 337860 KB Output is correct
7 Correct 3228 ms 337972 KB Output is correct
8 Correct 3128 ms 335460 KB Output is correct
9 Correct 2570 ms 334424 KB Output is correct
10 Correct 2685 ms 336516 KB Output is correct
11 Correct 2447 ms 332096 KB Output is correct
12 Correct 2668 ms 334660 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3493 ms 351424 KB Output is correct
2 Correct 3031 ms 347356 KB Output is correct
3 Correct 2684 ms 334604 KB Output is correct
4 Correct 2879 ms 337180 KB Output is correct
5 Correct 2651 ms 335636 KB Output is correct
6 Correct 3222 ms 335764 KB Output is correct
7 Correct 3446 ms 339124 KB Output is correct
8 Execution timed out 3518 ms 339268 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1447 ms 342160 KB Output is correct
2 Correct 1383 ms 338744 KB Output is correct
3 Correct 1030 ms 325524 KB Output is correct
4 Correct 1134 ms 325528 KB Output is correct
5 Correct 1161 ms 325720 KB Output is correct
6 Correct 1416 ms 329500 KB Output is correct
7 Correct 1377 ms 327596 KB Output is correct
8 Correct 1383 ms 325864 KB Output is correct
9 Correct 1328 ms 329972 KB Output is correct
10 Correct 1276 ms 328692 KB Output is correct
11 Correct 1304 ms 327920 KB Output is correct
12 Correct 1369 ms 327936 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3536 ms 397468 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 3514 ms 394244 KB Time limit exceeded
2 Halted 0 ms 0 KB -