oj.uz

답안 #292023

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
292023 2020-09-06T08:18:08 Z Diuven 서류 전달 (ROI16_sending) C++17
0 / 100
 12 ms 9984 KB 
/**
 * Author: Sergey Kopeliovich ([email protected])
 *
 * O(nlogn + mhlogn)
 * Насчитали за O(nlogn) двоичные подъёмы для LCA.
 * Насчитали за O(mh) для каждой вершины дерева список путей, проходящих через неё.
 * Фиксируем нижний конец пересечения A. Сортируем концы путей по порядку в Эйлервом Обходе, используя LCA смотрим ответы для соседних.
 */

#include <cassert>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>


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--)
#define sz(a) (int)(a).size()
#define pb push_back
#define all(a) (a).begin(), (a).end()

typedef pair <int, int> pii;

const int N = 1e5, K = 18;

int n, k, p[N], a[N], b[N], lca[N], dep[N];
vector<int> ids[N], c[N];
int an, pos[N], bn[2 * N];
int sparse[K][2 * N];

inline void mark( int v, int i ) {
	ids[v].pb(i);
}

void dfs( int v, int d = 0, int p = -1 ) {
	pos[v] = an, dep[v] = sparse[0][an++] = d;
	for (int x : c[v])
		if (x != p)
			dfs(x, d + 1, v), sparse[0][an++] = d;
}

inline int getLcaDepth( int a, int b ) {
	a = pos[a], b = pos[b];
	if (a > b)
		swap(a, b);
	int k = bn[++b - a];
	assert(k < K);
	return min(sparse[k][a], sparse[k][b - (1 << k)]);
}

int ma = 0, ri = 0, rj = 1;

void relax( int i, int j ) {
	if (i == j) return;
	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;
}

int main() {
	#define NAME "twopaths"
	assert(freopen(NAME ".in", "r", stdin));
	assert(freopen(NAME ".out", "w", stdout));

	scanf("%d%d", &n, &k);
	assert(n <= N && k <= N);
	for (int i = 1; i < n; i++) {
		scanf("%d", &p[i]), p[i]--;
		c[i].pb(p[i]), c[p[i]].pb(i);
	}
	dfs(0);
	for (int i = 2; i <= an; i++)
		bn[i] = bn[i >> 1] + 1;
	forn(k, K - 1)
		forn(i, an - (1 << k) + 1)
			sparse[k + 1][i] = min(sparse[k][i], sparse[k][i + (1 << k)]);

	forn(i, k) {
		scanf("%d%d", &a[i], &b[i]), a[i]--, b[i]--;
		lca[i] = getLcaDepth(a[i], b[i]);
		int v = a[i], u = b[i];
		while (dep[v] > dep[u])
			mark(v, i), v = p[v];
		while (dep[u] > dep[v])
			mark(u, i), u = p[u];
		while (v != u) {
			mark(v, i), v = p[v];
			mark(u, i), u = p[u];
		}
		mark(v, i);
	}
	vector<pii> et;
	forn(v, n) {
		et.clear();
		for (int x : ids[v]) {
			et.pb(pii(pos[a[x]], x));
			et.pb(pii(pos[b[x]], x));
		}
		sort(all(et));
		forn(i, sz(et) - 1)
			relax(et[i].second, et[i + 1].second);
	}
	printf("%d\n", ma);
	printf("%d %d\n", ri + 1, rj + 1);
}

Compilation message

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

Subtask #1
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 11 ms 9888 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 12 ms 9984 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -