oj.uz

Submission #634042

# Submission time Handle Problem Language Result Execution time Memory
634042 2022-08-23T17:52:57 Z valerikk Prize (CEOI22_prize) C++17
100 / 100
 2825 ms 408460 KB 
#include <bits/stdc++.h>

using namespace std;

#define x first
#define y second
#define all(a) begin(a), end(a)
#define sz(a) ((int) (a).size())

using ll = long long;
using ld = long double;

const int N = 1e6 + 11;
const int L = 20;

vector<int> get_lis(const vector<int> &a) {
	vector<pair<int, int>> dp{{-1, -1}};
	vector<int> par(sz(a));
	for (int i = 0; i < sz(a); ++i) {
		int ind = lower_bound(all(dp), make_pair(a[i], -1)) - begin(dp);
		par[i] = dp[ind - 1].y;
		if (ind == sz(dp)) {
			dp.push_back({a[i], i});
		} else {
			dp[ind] = {a[i], i};
		}
	}
	vector<int> ret;
	for (int i = dp.back().y; i != -1; i = par[i]) {
		ret.push_back(i);
	}
	reverse(all(ret));
	return ret;
}

int n, k, q, T;

struct Tree {
	vector<int> g[N];
	int p[N];
	int root;
	vector<int> ord;
	int tin[N], tout[N], t;
	int par[L][N];
	vector<pair<int, ll>> gr[N];
	ll d[N];
	bool vis[N];

	bool is_par(int u, int v) {
		return tin[u] <= tin[v] && tout[u] >= tout[v];
	}

	int get_lca(int u, int v) {
		if (is_par(u, v)) return u;
		if (is_par(v, u)) return v;
		for (int i = L - 1; i >= 0; --i) {
			if (!is_par(par[i][u], v)) u = par[i][u];
		}
		return p[u];
	}

	ll get_dist(int u, int v) {
		return d[u] + d[v] - 2 * d[get_lca(u, v)];
	}

	void dfs(int u) {
		tin[u] = t++;
		ord.push_back(u);
		for (int v : g[u]) {
			dfs(v);
		}
		tout[u] = t;
	}

	void add_edge(int u, int v, ll w) {
		if (tin[u] > tin[v]) swap(u, v);
		gr[u].push_back({v, w});
		gr[v].push_back({u, -w});
	}

	void go(int u, int k, vector<int> &x) {
		if (sz(x) < k) {
			x.push_back(u);
		}
		for (int v : g[u]) {
			go(v, k, x);
		}
	}

	void calc_depths() {
		fill(all(vis), false);
		queue<int> q;
		for (int s = 0; s < n; ++s) {
			if (!vis[s]) {
				q.push(s);
				d[s] = 0;
				vis[s] = true;
				while (!q.empty()) {
					int u = q.front();
					q.pop();
					for (const auto &[v, w] : gr[u]) {
						if (!vis[v]) {
							vis[v] = true;
							d[v] = d[u] + w;
							q.push(v);
						}
					}
				}
			}
		}
	}

	void build() {
		t = 0;
		ord.clear();
		ord.reserve(n);
		dfs(root);
		for (int i = 0; i < n; ++i) {
			par[0][i] = p[i];
		}
		par[0][root] = root;
		for (int i = 1; i < L; ++i) {
			for (int j = 0; j < n; ++j) {
				par[i][j] = par[i - 1][par[i - 1][j]];
			}
		}
	}

	void read() {
		for (int i = 0; i < n; ++i) {
			scanf("%d", &p[i]);
			if (p[i] == -1) {
				root = i;
			} else {
				--p[i];
				g[p[i]].push_back(i);
			}
		}
	}
} t1, t2;

int main() {
	scanf("%d %d %d %d", &n, &k, &q, &T);
	t1.read();
	t2.read();
	t1.build();
	t2.build();
	vector<int> x;
	t1.go(t1.root, k, x);
	sort(all(x), [&](int u, int v) {
		return t2.tin[u] < t2.tin[v];
	});
	for (int i = 0; i < k; ++i) {
		printf("%d", x[i] + 1);
		if (i != k - 1) printf(" ");
	}
	printf("\n");
	fflush(stdout);
	for (int i = 1; i < k; ++i) {
		printf("? %d %d\n", x[i - 1] + 1, x[i] + 1);
	}
	printf("!\n");
	fflush(stdout);
	static int d[4];
	for (int i = 1; i < k; ++i) {
		scanf("%d %d %d %d", &d[0], &d[1], &d[2], &d[3]);
		int z1 = t1.get_lca(x[i - 1], x[i]);
		t1.add_edge(z1, x[i - 1], d[0]);
		t1.add_edge(z1, x[i], d[1]);
		int z2 = t2.get_lca(x[i - 1], x[i]);
		t2.add_edge(z2, x[i - 1], d[2]);
		t2.add_edge(z2, x[i], d[3]);
	}
	t1.calc_depths();
	t2.calc_depths();
	vector<pair<int, int>> ans(T);
	for (int i = 0; i < T; ++i) {
		int p, q;
		scanf("%d %d", &p, &q);
		--p, --q;
		ans[i] = {(int)t1.get_dist(p, q), (int)t2.get_dist(p, q)};
	}
	for (int i = 0; i < T; ++i) {
		printf("%d %d\n", ans[i].x, ans[i].y);
	}
	fflush(stdout);
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:143:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  143 |  scanf("%d %d %d %d", &n, &k, &q, &T);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   scanf("%d %d %d %d", &d[0], &d[1], &d[2], &d[3]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:179:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |   scanf("%d %d", &p, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp: In member function 'void Tree::read()':
Main.cpp:131:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |    scanf("%d", &p[i]);
      |    ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 255816 KB Output is correct
2 Correct 960 ms 260024 KB Output is correct
3 Correct 1273 ms 227616 KB Output is correct
4 Correct 1236 ms 226796 KB Output is correct
5 Correct 1332 ms 231240 KB Output is correct
6 Correct 1377 ms 235804 KB Output is correct
7 Correct 1385 ms 235744 KB Output is correct
8 Correct 1345 ms 234640 KB Output is correct
9 Correct 1278 ms 227288 KB Output is correct
10 Correct 1325 ms 230020 KB Output is correct
11 Correct 1228 ms 225128 KB Output is correct
12 Correct 1377 ms 229240 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 260392 KB Output is correct
2 Correct 915 ms 253956 KB Output is correct
3 Correct 1441 ms 227256 KB Output is correct
4 Correct 1560 ms 231056 KB Output is correct
5 Correct 1494 ms 228208 KB Output is correct
6 Correct 1514 ms 232304 KB Output is correct
7 Correct 1712 ms 237340 KB Output is correct
8 Correct 1704 ms 237868 KB Output is correct
9 Correct 1693 ms 235408 KB Output is correct
10 Correct 1749 ms 236844 KB Output is correct
11 Correct 1515 ms 231088 KB Output is correct
12 Correct 1728 ms 236412 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 244828 KB Output is correct
2 Correct 767 ms 244764 KB Output is correct
3 Correct 619 ms 215064 KB Output is correct
4 Correct 611 ms 215012 KB Output is correct
5 Correct 610 ms 214960 KB Output is correct
6 Correct 720 ms 221968 KB Output is correct
7 Correct 712 ms 221888 KB Output is correct
8 Correct 708 ms 221884 KB Output is correct
9 Correct 662 ms 219700 KB Output is correct
10 Correct 645 ms 219620 KB Output is correct
11 Correct 654 ms 219684 KB Output is correct
12 Correct 675 ms 219564 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1793 ms 392928 KB Output is correct
2 Correct 1786 ms 392916 KB Output is correct
3 Correct 1461 ms 333172 KB Output is correct
4 Correct 1481 ms 333088 KB Output is correct
5 Correct 1477 ms 333248 KB Output is correct
6 Correct 1875 ms 347080 KB Output is correct
7 Correct 1890 ms 346976 KB Output is correct
8 Correct 1850 ms 346908 KB Output is correct
9 Correct 1851 ms 342588 KB Output is correct
10 Correct 1815 ms 342624 KB Output is correct
11 Correct 1747 ms 342388 KB Output is correct
12 Correct 1777 ms 342548 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1925 ms 408460 KB Output is correct
2 Correct 1895 ms 407556 KB Output is correct
3 Correct 2214 ms 343760 KB Output is correct
4 Correct 2390 ms 350104 KB Output is correct
5 Correct 2097 ms 342884 KB Output is correct
6 Correct 2714 ms 364072 KB Output is correct
7 Correct 2534 ms 357344 KB Output is correct
8 Correct 2825 ms 361160 KB Output is correct
9 Correct 2726 ms 355416 KB Output is correct
10 Correct 2527 ms 353816 KB Output is correct
11 Correct 2393 ms 353832 KB Output is correct
12 Correct 2574 ms 356840 KB Output is correct