oj.uz

Submission #906124

# Submission time Handle Problem Language Result Execution time Memory
906124 2024-01-13T14:24:18 Z MilosMilutinovic Prize (CEOI22_prize) C++14
19 / 100
 3500 ms 395928 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 3034 ms 346868 KB Output is correct
2 Execution timed out 3574 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 3553 ms 351320 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1542 ms 342108 KB Output is correct
2 Correct 1761 ms 338808 KB Output is correct
3 Correct 1263 ms 325616 KB Output is correct
4 Correct 1241 ms 320404 KB Output is correct
5 Correct 1286 ms 325516 KB Output is correct
6 Correct 1567 ms 326212 KB Output is correct
7 Correct 1633 ms 327464 KB Output is correct
8 Correct 1517 ms 325840 KB Output is correct
9 Correct 1436 ms 329980 KB Output is correct
10 Correct 1397 ms 328688 KB Output is correct
11 Correct 1322 ms 327916 KB Output is correct
12 Correct 1412 ms 327868 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3524 ms 395928 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 3594 ms 394452 KB Time limit exceeded
2 Halted 0 ms 0 KB -