Submission #644101

# Submission time Handle Problem Language Result Execution time Memory
644101 2022-09-23T19:47:45 Z kingfran1907 Prize (CEOI22_prize) C++14
0 / 100
1531 ms 433440 KB
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 1e6+10;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
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]);

	while (t--) {
		int a, b;
		scanf("%d%d", &a, &b);
		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

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:134:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Execution timed out 663 ms 266276 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 776 ms 269124 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 566 ms 257632 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1244 ms 421356 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1531 ms 433440 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -