Submission #291905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
291905	2020-09-06T01:49:38 Z	Diuven	ROI16_sending (ROI16_sending)	C++17	Compilation error	0 ms	0 KB

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() {
	freopen("twopaths.in", "r", stdin);
	freopen("twopaths.out", "w", stdout);
	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

In file included from /usr/include/c++/9/set:60,
                 from sending.cpp:3:
/usr/include/c++/9/bits/stl_tree.h: In instantiation of 'static const _Key& std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_S_key(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp; _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Const_Link_type = const std::_Rb_tree_node<std::pair<int, int> >*]':
/usr/include/c++/9/bits/stl_tree.h:1929:36:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_lower_bound(std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type, std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr, const _Key&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp; _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Link_type = std::_Rb_tree_node<std::pair<int, int> >*; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Base_ptr = std::_Rb_tree_node_base*]'
/usr/include/c++/9/bits/stl_tree.h:1282:56:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Val = std::pair<int, int>; _KeyOfValue = std::_Identity<std::pair<int, int> >; _Compare = cmp; _Alloc = std::allocator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator = std::_Rb_tree_iterator<std::pair<int, int> >; std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::key_type = std::pair<int, int>]'
/usr/include/c++/9/bits/stl_set.h:830:36:   required from 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::lower_bound(const key_type&) [with _Key = std::pair<int, int>; _Compare = cmp; _Alloc = std::allocator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree_const_iterator<std::pair<int, int> >; std::set<_Key, _Compare, _Alloc>::key_type = std::pair<int, int>]'
sending.cpp:62:39:   required from here
/usr/include/c++/9/bits/stl_tree.h:780:8: error: static assertion failed: comparison object must be invocable as const
  780 |        is_invocable_v<const _Compare&, const _Key&, const _Key&>,
      |        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sending.cpp: In function 'int main()':
sending.cpp:93:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  freopen("twopaths.in", "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
sending.cpp:94:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   94 |  freopen("twopaths.out", "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
sending.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
sending.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   97 |   scanf("%d", &u), --u;
      |   ~~~~~^~~~~~~~~~
sending.cpp:117:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  117 |   scanf("%d%d", &u, &v), --u, --v;
      |   ~~~~~^~~~~~~~~~~~~~~~