Submission #291907

#	Time	Username	Problem	Language	Result	Execution time	Memory
291907		Diuven	ROI16_sending (ROI16_sending)	C++11	100 / 100	2584 ms	212192 KiB

sending

#include <cassert>
#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define data __data
using namespace std;

const int L = 19;
const int N = (int) 2e5 + 10;
int n, m, curt, u, v, opt = 0, opti = 0, optj = 1, h[N], firstoc[N], order[2 * N], p[2 * N][L], mx[2 * N], curpos;
vector<int> adj[N];
typedef pair<int, int> tpath;
vector<tpath> paths[N], die[N];

struct cmp {
	bool operator()(tpath a, tpath b) {
		return (mp(firstoc[a.fs], a.sc) < mp(firstoc[b.fs], b.sc));
	}
};

typedef set< tpath, cmp > tpathset;
tpathset data[N];

void dfs(int v, int pv = -1) {
	firstoc[v] = curpos;
	order[curpos++] = v;
	for (int u : adj[v]) {
		if (u != pv) {
			h[u] += h[v];
			dfs(u, v);
			order[curpos++] = v;
		}
	}
}

int plusik(int a, int b) {
	return (h[a] < h[b]) ? a : b;
}

int lca(int u, int v) {
	u = firstoc[u], v = firstoc[v];
	if (u > v) {
		swap(u, v);
	}
	int k = mx[v - u + 1];
	return plusik(p[u][k], p[v - (1 << k) + 1][k]);
}

void relax(int v, tpath path1, tpath path2) {
	int res = h[v] - h[lca(v, path1.fs)] - h[lca(v, path2.fs)] + h[lca(path1.fs, path2.fs)];
	if (res > opt) {
		opt = res, opti = path1.sc, optj = path2.sc;
	}
}

void add(int v, tpath path) {
	auto match = data[v].lower_bound(path);
	if (match != data[v].end()) {
		relax(v, path, *match);
	}
	if (match != data[v].begin()) {
		relax(v, path, *(--match));
	}
	data[v].insert(path);
}

void solve(int v, int pv = -1) {
	for (int u : adj[v]) {
		if (u != pv) {
			solve(u, v);
			if (sz(data[v]) < sz(data[u])) {
				data[v].swap(data[u]);
			}
			for (tpath path : data[u]) {
				add(v, path);
			}
		}
	}
	for (tpath path : paths[v]) {
		add(v, path);
	}
	for (tpath path : die[v]) {
		data[v].erase(path);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; ++i) {
		scanf("%d", &u), --u;
		adj[u].pb(i), adj[i].pb(u);
	}
	for (int i = 1; i < n; ++i)
		h[i] = 1;
	dfs(0, -1);
	mx[1] = 0;
	for (int i = 2; i < curpos; ++i) {
		mx[i] = mx[i - 1];
		if (i == (1 << (mx[i] + 1))) {
			mx[i]++;
		}
	}
	for (int i = 0; i < curpos; ++i)
		p[i][0] = order[i];
	for (int j = 1; j < L; ++j)
		for (int i = 0; i + (1 << j) <= curpos; ++i) {
			p[i][j] = plusik(p[i][j - 1], p[i + (1 << (j - 1))][j - 1]);
		}
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v), --u, --v;
		paths[u].pb(mp(v, i)), paths[v].pb(mp(u, i));
		int w = lca(u, v);
		die[w].pb(mp(v, i)), die[w].pb(mp(u, i));
	}
	solve(0, -1);
	printf("%d\n%d %d\n", opt, opti + 1, optj + 1);
	return 0;
}

Compilation message (stderr)

sending.cpp: In function 'int main()':
sending.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:95:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |   scanf("%d", &u), --u;
      |   ~~~~~^~~~~~~~~~
sending.cpp:115:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  115 |   scanf("%d%d", &u, &v), --u, --v;
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 29 / 29
• Subtask 2: 12 / 12
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 10 / 10
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 10 / 10