oj.uz

Submission #1024905

# Submission time Handle Problem Language Result Execution time Memory
1024905 2024-07-16T12:10:09 Z thinknoexit City Mapping (NOI18_citymapping) C++17
Compilation error
 0 ms 0 KB 
#include "citymapping.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1010;
mt19937 rnd(time(NULL));
int n;
ll dis[N][N];
int A[N], B[N], W[N], tot;
ll d(int i, int j) {
	if (i == j) return 0;
	if (!dis[i][j]) return dis[i][j] = dis[j][i] = get_distance(i, j);
	return dis[i][j];
}
void play(vector<int>& v, int U, int V) {
	int m = v.size();
	if (m == 1) return;
	ll all = d(U, V);
	vector<pair<ll, int>> in, rem;
	for (auto& x : v) {
		if (d(U, x) + d(x, V) == all) in.push_back({ d(V, x), x });
		else {
			ll extra = (d(U, x) + d(x, V) - all) / 2;
			rem.push_back({ d(V, x) - extra, x });
		}
	}
	sort(in.begin(), in.end());
	sort(rem.begin(), rem.end());
	vector<vector<int>> r;
	vector<int> p2, p3;
	int p = 0;
	for (int i = 1;i < (int)in.size();i++) {
		A[tot] = in[i - 1].second;
		B[tot] = in[i].second;
		W[tot] = in[i].first - in[i - 1].first;
		tot++;
		vector<int> nw;
		ll mn = LLONG_MAX;
		int idx = 0;
		while (p < (int)rem.size() && rem[p].first == in[i].first) {
			int vl = rem[p].second;
			ll extra = (d(U, vl) + d(vl, V) - all) / 2;
			if (extra < mn) {
				mn = extra;
				idx = vl;
			}
			nw.push_back(vl);
			p++;
		}
		if ((int)nw.size() >= 2) {
			A[tot] = idx;
			B[tot] = in[i].second;
			W[tot] = mn;
			tot++;
			ll mx = -1;
			int idx2 = 0;
			for (auto& x : nw) {
				dis[idx][x] = dis[x][idx] = d(V, x) - mn - in[i].first;
				if (dis[idx][x] > mx) {
					mx = dis[idx][x];
					idx2 = x;
				}
			}
			sort(nw.begin(), nw.end(), [&] {
				return d(p2[i], a) < d(p2[i], b);
				});
			r.push_back(nw);
		}
	}
	for (int i = 0;i < (int)r.size();i++) {
		play(r[i], r[i][r[i].size() - 2], r[i][r[i].size() - 1]);
	}
}
void find_roads(int NN, int Q, int A[], int B[], int W[]) {
	n = NN;
	vector<int> init(n);
	int rt = rnd() % n + 1;
	iota(init.begin(), init.end(), 1);
	int leaf = 0, leaf2 = 0;
	ll mx = -1;
	for (int i = 1;i <= n;i++) {
		if (d(rt, i) > mx) {
			mx = d(rt, i);
			leaf = i;
		}
	}
	sort(init.begin(), init.end(), [&](int a, int b) {
		return d(rt, a) < d(rt, b);
		});
	play(init, init[n - 2], init[n - 1]);
	for (int i = 0;i < n - 1;i++) {
		A[i] = ::A[i];
		B[i] = ::B[i];
		W[i] = ::W[i];
		//cout << A[i] << ' ' << B[i] << ' ' << W[i] << '\n';
	}
	return;
}

Compilation message

citymapping.cpp: In lambda function:
citymapping.cpp:65:21: error: 'a' was not declared in this scope
   65 |     return d(p2[i], a) < d(p2[i], b);
      |                     ^
citymapping.cpp:65:35: error: 'b' was not declared in this scope
   65 |     return d(p2[i], a) < d(p2[i], b);
      |                                   ^
citymapping.cpp: In function 'void find_roads(int, int, int*, int*, int*)':
citymapping.cpp:79:16: warning: unused variable 'leaf2' [-Wunused-variable]
   79 |  int leaf = 0, leaf2 = 0;
      |                ^~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from citymapping.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Iterator2 = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = play(std::vector<int>&, int, int)::<lambda()>]':
/usr/include/c++/10/bits/stl_algo.h:82:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1924:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1958:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = play(std::vector<int>&, int, int)::<lambda()>]'
citymapping.cpp:66:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:156:30: error: no match for call to '(play(std::vector<int>&, int, int)::<lambda()>) (int&, int&)'
  156 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                       ~~~~~~~^~~~~~~~~~~~~~~~
citymapping.cpp:64:31: note: candidate: 'play(std::vector<int>&, int, int)::<lambda()>'
   64 |    sort(nw.begin(), nw.end(), [&] {
      |                               ^
citymapping.cpp:64:31: note:   candidate expects 0 arguments, 2 provided
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from citymapping.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = int; _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = play(std::vector<int>&, int, int)::<lambda()>]':
/usr/include/c++/10/bits/stl_algo.h:1826:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Val_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1886:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1977:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = play(std::vector<int>&, int, int)::<lambda()>]'
citymapping.cpp:66:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:238:23: error: no match for call to '(play(std::vector<int>&, int, int)::<lambda()>) (int&, int&)'
  238 |  { return bool(_M_comp(__val, *__it)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
citymapping.cpp:64:31: note: candidate: 'play(std::vector<int>&, int, int)::<lambda()>'
   64 |    sort(nw.begin(), nw.end(), [&] {
      |                               ^
citymapping.cpp:64:31: note:   candidate expects 0 arguments, 2 provided
In file included from /usr/include/c++/10/bits/stl_algobase.h:71,
                 from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from citymapping.cpp:2:
/usr/include/c++/10/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Value = int; _Compare = play(std::vector<int>&, int, int)::<lambda()>]':
/usr/include/c++/10/bits/stl_heap.h:139:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_heap.h:246:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_heap.h:355:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1666:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1937:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1953:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:1974:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<play(std::vector<int>&, int, int)::<lambda()> >]'
/usr/include/c++/10/bits/stl_algo.h:4892:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = __gnu_cxx::__normal_iterator<int*, std::vector<int> >; _Compare = play(std::vector<int>&, int, int)::<lambda()>]'
citymapping.cpp:66:6:   required from here
/usr/include/c++/10/bits/predefined_ops.h:194:23: error: no match for call to '(play(std::vector<int>&, int, int)::<lambda()>) (int&, int&)'
  194 |  { return bool(_M_comp(*__it, __val)); }
      |                ~~~~~~~^~~~~~~~~~~~~~
citymapping.cpp:64:31: note: candidate: 'play(std::vector<int>&, int, int)::<lambda()>'
   64 |    sort(nw.begin(), nw.end(), [&] {
      |                               ^
citymapping.cpp:64:31: note:   candidate expects 0 arguments, 2 provided