Submission #634042

#	Time	Username	Problem	Language	Result	Execution time	Memory
634042		valerikk	Prize (CEOI22_prize)	C++17	100 / 100	2825 ms	408460 KiB

Main

#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 (stderr)

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 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24