oj.uz

Submission #1119539

# Submission time Handle Problem Language Result Execution time Memory
1119539 2024-11-27T06:26:23 Z vjudge1 Min-max tree (BOI18_minmaxtree) C++17
Compilation error
 0 ms 0 KB 
#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second

using namespace std;
using ll = long long;
using pii = pair <int, int>;
const int N = 2e5 + 5, inf = 1e9;

int n, sz[N], d[N], ind[N], par[N], ct, tp[N], l[N], r[N], node[N];
vector <int> g[N], gg[N], add[N][2], del[N][2];
char C[N];
int U[N], V[N], Z[N], used[N], timer, Mt[N];

void calc(int v, int p = 0) {
	sz[v] = 1;
	par[v] = p;
	for (auto to : g[v]) {
		if (to != p) {
			d[to] = d[v] + 1;
			calc(to, v);
			sz[v] += sz[to];
		}
	}
}
void dfs(int v, int p = 0, int top = 1) {
	ind[v] = ++ct;
	node[ind[v]] = v;
	tp[v] = top;
	int mx = 0, bg = -1;
	for (auto to : g[v]) {
		if (to != p && mx < sz[to]) 
			mx = sz[to], bg = to;
	}
	if (bg != -1)
		dfs(bg, v, top);
	for (auto to : g[v]) {
		if (to != p && to != bg)
			dfs(to, v, to);
	}
}

bool kuhn(int v) {
	if (used[v] == timer)
		return 0;
	used[v] = timer;
	for (auto to : gg[v]) {
		if (Mt[to] != -1) {
			Mt[to] = v;
			return 1;
		}
	}
	for (auto to : gg[v]) {
		if (kuhn(Mt[to])) {
			Mt[to] = v;
			return 1;
		}
	}
	return 0;
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1, u, v; i < n; ++i) {
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	calc(1);
	dfs(1);
	int q;
	cin >> q;
	for (int i = 0; i < q; ++i) {
		char c;
		int u, v, z;
		cin >> c >> u >> v >> z;
		C[i] = c;
		U[i] = u;
		V[i] = v;
		Z[i] = z;
		
		int mn = inf;
		vector <pii> seg;
		while (tp[u] != tp[v]) {
			if (d[tp[u]] < d[tp[v]]) swap(u, v);
			seg.pb({ind[tp[u]], ind[u]});
			mn = min(mn, seg.back().f);
			u = par[tp[u]];
		}
		if (d[u] > d[v]) swap(u, v);
		seg.pb({ind[u], ind[v]});
		mn = min(mn, seg.back().f);
		
		for (auto [l, r] : seg) {
			if (l == mn)
				++l;
			add[l][(c == 'm')].pb(z);
			del[r + 1][(c == 'm')].pb(z);
		}
	}
	multiset <int> mt[2];
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < 2; ++j) {
			for (auto z : add[i][j])
				mt[j].insert(z);
			for (auto z : del[i][j])
				mt[j].erase(mt[j].find(z));
		}
		r[i] = inf;
		if (sz(mt[0]))
			r[i] = *mt[0].begin();
		if (sz(mt[1]))
			l[i] = *mt[1].rbegin();
	}
	if (n > 1000) {
		for (int i = 1; i <= n; ++i) {
			if (par[i])
				cout << i << ' ' << par[i] << ' ' << r[ind[i]] << '\n';
		}
		return 0;
	}
	for (int i = 0; i < q; ++i) {
		char c;
		int u, v, z;
		c = C[i];
		u = U[i];
		v = V[i];
		z = Z[i];
		
		int mn = inf;
		vector <pii> seg;
		while (tp[u] != tp[v]) {
			if (d[tp[u]] < d[tp[v]]) swap(u, v);
			seg.pb({ind[tp[u]], ind[u]});
			mn = min(mn, seg.back().f);
			u = par[tp[u]];
		}
		if (d[u] > d[v]) swap(u, v);
		seg.pb({ind[u], ind[v]});
		mn = min(mn, seg.back().f);
		
		for (auto [x, y] : seg) {
			if (x == mn)
				++x;
			
			for (int j = x; j <= y; ++j) {
				if (c == 'm' && l[j] == z) {
					gg[i].pb(j + q);
					cout << i << ' ' << j + q << '\n';
				}
				if (c == 'M' && r[j] == z) {
					cout << i << ' ' << j + q << '\n';
					gg[i].pb(j + q);
				}
			}
		}
	}
	for (int i = 1; i <= n; ++i)
		Mt[i] = -1;
	for (int i = 0; i < q; ++i) {
		++timer;
		kuhn(i);
	}
	set <int> st;
	for (int i = 1; i <= n; ++i)
		st.insert(mt[i + q]);
	assert(sz(st) == q);
	for (int i = 1; i <= n; ++i) {
		if (!par[i])
			continue;
		if (Mt[ind[i] + q] == -1)
			cout << i << ' ' << par[i] << ' ' << l[ind[i]] << '\n';
		else
			cout << i << ' ' << par[i] << ' ' << Z[Mt[ind[i] + q]] << '\n';
	}
	return 0;
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:171:22: error: no matching function for call to 'std::set<int>::insert(std::multiset<int>&)'
  171 |   st.insert(mt[i + q]);
      |                      ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from minmaxtree.cpp:1:
/usr/include/c++/10/bits/stl_set.h:509:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = int]'
  509 |       insert(const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:509:32: note:   no known conversion for argument 1 from 'std::multiset<int>' to 'const value_type&' {aka 'const int&'}
  509 |       insert(const value_type& __x)
      |              ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:518:7: note: candidate: 'std::pair<typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator, bool> std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; typename std::_Rb_tree<_Key, _Key, std::_Identity<_Tp>, _Compare, typename __gnu_cxx::__alloc_traits<_Alloc>::rebind<_Key>::other>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = int]'
  518 |       insert(value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:518:27: note:   no known conversion for argument 1 from 'std::multiset<int>' to 'std::set<int>::value_type&&' {aka 'int&&'}
  518 |       insert(value_type&& __x)
      |              ~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:546:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, const value_type&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = int]'
  546 |       insert(const_iterator __position, const value_type& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:546:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:551:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::value_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::value_type = int]'
  551 |       insert(const_iterator __position, value_type&& __x)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:551:7: note:   candidate expects 2 arguments, 1 provided
/usr/include/c++/10/bits/stl_set.h:566:2: note: candidate: 'template<class _InputIterator> void std::set<_Key, _Compare, _Alloc>::insert(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  566 |  insert(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~
/usr/include/c++/10/bits/stl_set.h:566:2: note:   template argument deduction/substitution failed:
minmaxtree.cpp:171:22: note:   candidate expects 2 arguments, 1 provided
  171 |   st.insert(mt[i + q]);
      |                      ^
In file included from /usr/include/c++/10/set:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:87,
                 from minmaxtree.cpp:1:
/usr/include/c++/10/bits/stl_set.h:578:7: note: candidate: 'void std::set<_Key, _Compare, _Alloc>::insert(std::initializer_list<_Tp>) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>]'
  578 |       insert(initializer_list<value_type> __l)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:578:43: note:   no known conversion for argument 1 from 'std::multiset<int>' to 'std::initializer_list<int>'
  578 |       insert(initializer_list<value_type> __l)
      |              ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_set.h:598:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::insert_return_type std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::set<_Key, _Compare, _Alloc>::insert_return_type = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::insert_return_type; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::node_type]'
  598 |       insert(node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:598:26: note:   no known conversion for argument 1 from 'std::multiset<int>' to 'std::set<int>::node_type&&' {aka 'std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::node_type&&'}
  598 |       insert(node_type&& __nh)
      |              ~~~~~~~~~~~~^~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note: candidate: 'std::set<_Key, _Compare, _Alloc>::iterator std::set<_Key, _Compare, _Alloc>::insert(std::set<_Key, _Compare, _Alloc>::const_iterator, std::set<_Key, _Compare, _Alloc>::node_type&&) [with _Key = int; _Compare = std::less<int>; _Alloc = std::allocator<int>; std::set<_Key, _Compare, _Alloc>::iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::const_iterator = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::const_iterator; std::set<_Key, _Compare, _Alloc>::node_type = std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::node_type]'
  603 |       insert(const_iterator __hint, node_type&& __nh)
      |       ^~~~~~
/usr/include/c++/10/bits/stl_set.h:603:7: note:   candidate expects 2 arguments, 1 provided