Submission #644102

#	Time	Username	Problem	Language	Result	Execution time	Memory
644102		kingfran1907	Prize (CEOI22_prize)	C++14	100 / 100	2229 ms	538292 KiB

Main

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 2e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 21;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, k, q, t;
int parr[2][maxn];
int root[2];
vector< int > graph[2][maxn];
vector< int > pre[2];
int pos[2][maxn];
int dis[2][maxn];
int dp[2][logo + 10][maxn];
int sol[2][maxn];
bool bio[maxn];
vector< pair<int, int> > edg[2][maxn];

void dfs(int ind, int x, int parr, int d) {
	pre[ind].push_back(x);
	dis[ind][x] = d;
	dp[ind][0][x] = parr;

	for (int tren : graph[ind][x]) {
		if (tren != parr) dfs(ind, tren, x, d + 1);
	}
}

bool cmp(int x, int y) {
	return pos[1][x] < pos[1][y];
}

int lif(int ind, int x, int val) {
	for (int i = 0; i <= logo; i++) {
		if (val & (1 << i)) x = dp[ind][i][x];
	}
	return x;
}

int lca(int ind, int x, int y) {
	if (dis[ind][x] > dis[ind][y]) x = lif(ind, x, dis[ind][x] - dis[ind][y]);
	else y = lif(ind, y, dis[ind][y] - dis[ind][x]);
	if (x == y) return x;
	
	for (int i = logo; i >= 0; i--) {
		if (dp[ind][i][x] != dp[ind][i][y]) {
			x = dp[ind][i][x];
			y = dp[ind][i][y];
		}
	}
	return dp[ind][0][x];
}

void solve(int ind, int x) {
	bio[x] = true;
	for (auto iter : edg[ind][x]) {
		int tren = iter.X;
		int cost = iter.Y;
		if (bio[tren]) continue;

		sol[ind][tren] = sol[ind][x] + cost;
		solve(ind, tren);
	}
}

int main() {
	scanf("%d%d%d%d", &n, &k, &q, &t);
	for (int i = 0; i < 2; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &parr[i][j]);
			if (parr[i][j] == -1) root[i] = j;
			else graph[i][parr[i][j]].push_back(j);
		}
	}
	dfs(0, root[0], 0, 0); dfs(1, root[1], 1, 0);
	for (int p = 0; p < 2; p++) 
		for (int i = 1; i <= logo; i++)
			for (int j = 1; j <= n; j++)
				dp[p][i][j] = dp[p][i - 1][dp[p][i - 1][j]];

	for (int p = 0; p < 2; p++) 
		for (int i = 0; i < n; i++) 
			pos[p][pre[p][i]] = i;

	vector< int > v;
	for (int i = 1; i <= n; i++) {
		if (pos[0][i] < k) v.push_back(i);
	}
	sort(v.begin(), v.end(), cmp);

	assert(v.size() == k);
	for (int tren : v) printf("%d ", tren);
	printf("\n"); fflush(stdout);

	for (int i = 1; i < k; i++) {
		printf("? %d %d\n", v[i - 1], v[i]);
	}
	printf("!\n"); fflush(stdout);

	for (int i = 1; i < k; i++) {
		int x = v[i - 1], y = v[i];
		int a, b, c, d;
		scanf("%d %d %d %d", &a, &b, &c, &d);

		int lcaa = lca(0, x, y);
		int lcab = lca(1, x, y);
		edg[0][lcaa].push_back({x, a});
		edg[0][x].push_back({lcaa, -a});
		edg[0][lcaa].push_back({y, b});
		edg[0][y].push_back({lcaa, -b});

		edg[1][lcab].push_back({x, c});
		edg[1][x].push_back({lcab, -c});
		edg[1][lcab].push_back({y, d});
		edg[1][y].push_back({lcab, -d});
	}

	memset(bio, false, sizeof bio);
	solve(0, v[0]);
	memset(bio, false, sizeof bio);
	solve(1, v[0]);

	vector< pair<int, int> > qs;
	for (int i = 0; i < t; i++) {
		int a, b;
		scanf("%d%d", &a, &b);
		qs.push_back({a, b});
	}

	for (auto iter : qs) {
		int a = iter.X, b = iter.Y;
		int lc = lca(0, a, b);
		printf("%d ", sol[0][a] + sol[0][b] - 2 * sol[0][lc]);

		lc = lca(1, a, b);
		printf("%d\n", sol[1][a] + sol[1][b] - 2 * sol[1][lc]);
	}
	fflush(stdout);
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'int main()':
Main.cpp:100:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  100 |  assert(v.size() == k);
      |         ~~~~~~~~~^~~~
Main.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |  scanf("%d%d%d%d", &n, &k, &q, &t);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:79:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |    scanf("%d", &parr[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |   scanf("%d %d %d %d", &a, &b, &c, &d);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:135:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 25 / 25
• Subtask 3: 19 / 19
• Subtask 4: 22 / 22
• Subtask 5: 24 / 24