oj.uz

Submission #291909

# Submission time Handle Problem Language Result Execution time Memory
291909 2020-09-06T01:51:36 Z Diuven ROI16_sending (ROI16_sending) C++11
48 / 100
 5000 ms 7548 KB 
/**
 * Author: Sergey Kopeliovich ([email protected])
 *
 * O(m^2logn + nlogn)
 * Насчитали за O(nlogn) двоичные подъёмы для LCA.
 * Для каждой пары путей ищем пересечение за O(1).
 */

#include <cassert>
#include <cstdio>
#include <algorithm>

using namespace std;

#define forn(i, n) for (int i = 0; i < (int)(n); i++)
#define fornd(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

const int N = 1e5, K = 17;

int n, k, p[N][K], a[N], b[N], lca[N], dep[N];

void up( int &a, int k ) {
	fornd(i, K)
		if (k >= (1 << i))
			a = p[a][i], k -= 1 << i;
}

int getLcaDepth( int a, int b ) {
	up(a, dep[a] - dep[b]);
	up(b, dep[b] - dep[a]);
	fornd(i, K)
		if (p[a][i] != p[b][i])
			a = p[a][i], b = p[b][i];
	return dep[a == b ? a : p[a][0]];
}

int main() {

	scanf("%d%d", &n, &k);
	assert(n <= N && k <= N);
	p[0][0] = 0;
	for (int i = 1; i < n; i++) {
		scanf("%d", &p[i][0]);
		dep[i] = dep[--p[i][0]] + 1;
	}
	forn(k, K - 1)
		forn(i, n)
			p[i][k + 1] = p[p[i][k]][k];

	int ma = 0, ri = 0, rj = 1;
	forn(i, k) {
		scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
		lca[i] = getLcaDepth(a[i], b[i]);
		forn(j, i) { 
			int M = max(lca[i], lca[j]);
			#define F(a, b) max(0, getLcaDepth(a, b) - M)
			int sum = F(a[i], a[j]) + F(a[i], b[j]) + F(b[i], a[j]) + F(b[i], b[j]);
			if (ma < sum)
				ma = sum, ri = i, rj = j;
		}
	}
	printf("%d\n", ma);
	printf("%d %d\n", ri + 1, rj + 1);
}

Compilation message

sending.cpp: In function 'int main()':
sending.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%d", &p[i][0]);
      |   ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   52 |   scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
13 Correct 3 ms 256 KB Output is correct
14 Correct 3 ms 384 KB Output is correct
15 Correct 3 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 3 ms 384 KB Output is correct
19 Correct 3 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 282 ms 760 KB Output is correct
2 Correct 300 ms 648 KB Output is correct
3 Correct 380 ms 656 KB Output is correct
4 Correct 361 ms 648 KB Output is correct
5 Correct 361 ms 760 KB Output is correct
6 Correct 257 ms 648 KB Output is correct
7 Correct 358 ms 652 KB Output is correct
8 Correct 266 ms 640 KB Output is correct
9 Correct 270 ms 656 KB Output is correct
10 Correct 260 ms 652 KB Output is correct
11 Correct 85 ms 776 KB Output is correct
12 Correct 87 ms 648 KB Output is correct
13 Correct 377 ms 640 KB Output is correct
14 Correct 308 ms 640 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 409 ms 7416 KB Output is correct
2 Correct 427 ms 7416 KB Output is correct
3 Correct 719 ms 7404 KB Output is correct
4 Correct 774 ms 7404 KB Output is correct
5 Correct 609 ms 7288 KB Output is correct
6 Correct 280 ms 7404 KB Output is correct
7 Correct 711 ms 7420 KB Output is correct
8 Correct 298 ms 7416 KB Output is correct
9 Correct 327 ms 7296 KB Output is correct
10 Correct 285 ms 7400 KB Output is correct
11 Correct 139 ms 7396 KB Output is correct
12 Correct 98 ms 7296 KB Output is correct
13 Correct 666 ms 7404 KB Output is correct
14 Correct 462 ms 7400 KB Output is correct

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5027 ms 7436 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5098 ms 7440 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5032 ms 7544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5023 ms 7548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 384 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -