oj.uz

Submission #906128

# Submission time Handle Problem Language Result Execution time Memory
906128 2024-01-13T14:25:28 Z MilosMilutinovic Prize (CEOI22_prize) C++14
19 / 100
 3500 ms 397240 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 << endl;
	}
	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]) << endl;
	}
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 25.0

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

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1553 ms 342324 KB Output is correct
2 Correct 1478 ms 339044 KB Output is correct
3 Correct 1155 ms 325724 KB Output is correct
4 Correct 1140 ms 325520 KB Output is correct
5 Correct 1179 ms 325720 KB Output is correct
6 Correct 1512 ms 329780 KB Output is correct
7 Correct 1454 ms 327496 KB Output is correct
8 Correct 1409 ms 325764 KB Output is correct
9 Correct 1345 ms 330228 KB Output is correct
10 Correct 1359 ms 328680 KB Output is correct
11 Correct 1309 ms 328100 KB Output is correct
12 Correct 1357 ms 327912 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3564 ms 397240 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 3523 ms 395716 KB Time limit exceeded
2 Halted 0 ms 0 KB -