Submission #291910

#	Time	Username	Problem	Language	Result	Execution time	Memory
291910		Diuven	ROI16_sending (ROI16_sending)	C++11	100 / 100	4178 ms	194328 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 = 18;
const int N = (int) 2e5 + 10;
int n, m, curt, u, v, opt = 0, opti = 0, optj = 1, h[N], intime[N], outime[N], p[N][L];
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(intime[a.fs], a.sc) < mp(intime[b.fs], b.sc));
	}
};

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

void dfs(int v, int pv = -1) {
	intime[v] = curt++;
	for (int u : adj[v]) {
		if (u != pv) {
			p[u][0] = v;
			h[u] += h[v];
			dfs(u, v);
		}
	}
	outime[v] = curt++;
}

bool is_parent(int u, int v) {
	return (intime[u] <= intime[v]) && (outime[v] <= outime[u]);
}

int lca(int u, int v) {
	if (is_parent(u, v)) {
		return u;
	}
	for (int j = L - 1; j >= 0; --j) {
		if (!is_parent(p[u][j], v)) {
			u = p[u][j];
		}
	}
	return p[u][0];
}

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);
	for (int j = 1; j < L; ++j)
		for (int i = 0; i < n; ++i)
			p[i][j] = p[p[i][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:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:98:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   98 |   scanf("%d", &u), --u;
      |   ~~~~~^~~~~~~~~~
sending.cpp:108:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  108 |   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