oj.uz

Submission #644102

# Submission time Handle Problem Language Result Execution time Memory
644102 2022-09-23T19:55:10 Z kingfran1907 Prize (CEOI22_prize) C++14
100 / 100
 2229 ms 538292 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1097 ms 367028 KB Output is correct
2 Correct 1191 ms 369724 KB Output is correct
3 Correct 978 ms 321652 KB Output is correct
4 Correct 962 ms 320988 KB Output is correct
5 Correct 1020 ms 323580 KB Output is correct
6 Correct 1216 ms 332312 KB Output is correct
7 Correct 1175 ms 332500 KB Output is correct
8 Correct 1149 ms 331724 KB Output is correct
9 Correct 983 ms 321336 KB Output is correct
10 Correct 987 ms 322996 KB Output is correct
11 Correct 971 ms 319964 KB Output is correct
12 Correct 974 ms 322484 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1209 ms 369800 KB Output is correct
2 Correct 1078 ms 365832 KB Output is correct
3 Correct 974 ms 321504 KB Output is correct
4 Correct 1031 ms 323788 KB Output is correct
5 Correct 994 ms 322332 KB Output is correct
6 Correct 1133 ms 330340 KB Output is correct
7 Correct 1282 ms 333308 KB Output is correct
8 Correct 1257 ms 333852 KB Output is correct
9 Correct 1293 ms 331832 KB Output is correct
10 Correct 1197 ms 332368 KB Output is correct
11 Correct 1074 ms 328892 KB Output is correct
12 Correct 1152 ms 332188 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 725 ms 357036 KB Output is correct
2 Correct 738 ms 357176 KB Output is correct
3 Correct 596 ms 311028 KB Output is correct
4 Correct 606 ms 311044 KB Output is correct
5 Correct 579 ms 310976 KB Output is correct
6 Correct 683 ms 321032 KB Output is correct
7 Correct 671 ms 320964 KB Output is correct
8 Correct 703 ms 320932 KB Output is correct
9 Correct 666 ms 318904 KB Output is correct
10 Correct 670 ms 318792 KB Output is correct
11 Correct 658 ms 318864 KB Output is correct
12 Correct 639 ms 318820 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1781 ms 526184 KB Output is correct
2 Correct 1633 ms 526428 KB Output is correct
3 Correct 1360 ms 434188 KB Output is correct
4 Correct 1349 ms 433960 KB Output is correct
5 Correct 1330 ms 434032 KB Output is correct
6 Correct 1533 ms 453916 KB Output is correct
7 Correct 1620 ms 454356 KB Output is correct
8 Correct 1620 ms 454056 KB Output is correct
9 Correct 1506 ms 449836 KB Output is correct
10 Correct 1510 ms 450032 KB Output is correct
11 Correct 1570 ms 449900 KB Output is correct
12 Correct 1497 ms 449680 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 538292 KB Output is correct
2 Correct 1977 ms 537784 KB Output is correct
3 Correct 1704 ms 442868 KB Output is correct
4 Correct 1732 ms 446612 KB Output is correct
5 Correct 1591 ms 442140 KB Output is correct
6 Correct 2229 ms 466728 KB Output is correct
7 Correct 1892 ms 462472 KB Output is correct
8 Correct 1992 ms 465060 KB Output is correct
9 Correct 1819 ms 459936 KB Output is correct
10 Correct 1803 ms 458880 KB Output is correct
11 Correct 1831 ms 458940 KB Output is correct
12 Correct 1863 ms 461012 KB Output is correct