Submission #1315401

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315401		arkanefury	Roller Coaster Railroad (IOI16_railroad)	C++20	Compilation error	0 ms	0 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

#define pb push_back

ll ans;
int n, vsz, diff[400005], link[400005], sz[400005];
vector<int> vec;
vector<tuple<int, int, int> > ed;

int find(int x) {
	if (x == link[x]) return x;
	return link[x] = find(link[x]);
}

void unite(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	if (sz[b] > sz[a]) swap(a, b);
	sz[a] += sz[b];
	link[b] = a;
}

int disc(int x) {
	return lower_bound(vec.begin(), vec.end(), x) - vec.begin();
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
	s.pb(1e9);
	t.pb(1);
	n = s.size();
	for (int i = 0; i < n; i++)
		vec.pb(s[i]), vec.pb(t[i]);
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	for (int i = 0; i < n; i++) {
		diff[disc(s[i])]++;
		diff[disc(t[i])]--;
	}
	vsz = vec.size();
	for (int i = 0; i < vsz; i++) {
		link[i] = i;
		sz[i] = 1;
	}
	for (int i = 0; i < n; i++)
		unite(disc(s[i]), disc(t[i]));
	for (int i = 0, bal = 0; i < vsz; i++) {
		bal += diff[i];
		if (i == vsz - 1) assert(bal == 0);
		if (bal > 0) ans += (ll)bal * (ll)(vec[i + 1] - vec[i]);
		if (bal) unite(i, i + 1);
	}
	for (int i = 0; i < vsz - 1; i++) ed.emplace_back(vec[i + 1] - vec[i], i, i + 1);
	sort(ed.begin(), ed.end());
	for (auto [w, u, v] : ed)
		if (find(u) != find(v)) unite(u, v), ans += (ll)w;
	return ans;
}

Compilation message (stderr)

railroad.cpp:10:38: error: 'int link [400005]' redeclared as different kind of entity
   10 | int n, vsz, diff[400005], link[400005], sz[400005];
      |                                      ^
In file included from /usr/include/c++/13/bits/atomic_wait.h:45,
                 from /usr/include/c++/13/bits/atomic_base.h:42,
                 from /usr/include/c++/13/bits/shared_ptr_atomic.h:33,
                 from /usr/include/c++/13/memory:81,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:56,
                 from railroad.cpp:2:
/usr/include/unistd.h:819:12: note: previous declaration 'int link(const char*, const char*)'
  819 | extern int link (const char *__from, const char *__to)
      |            ^~~~
railroad.cpp: In function 'int find(int)':
railroad.cpp:15:24: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   15 |         if (x == link[x]) return x;
      |                        ^
railroad.cpp:15:15: error: ISO C++ forbids comparison between pointer and integer [-fpermissive]
   15 |         if (x == link[x]) return x;
      |             ~~^~~~~~~~~~
railroad.cpp:16:22: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   16 |         return link[x] = find(link[x]);
      |                      ^
railroad.cpp:16:37: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   16 |         return link[x] = find(link[x]);
      |                                     ^
railroad.cpp:16:30: error: no matching function for call to 'find(int (&)(const char*, const char*) noexcept)'
   16 |         return link[x] = find(link[x]);
      |                          ~~~~^~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/stl_algo.h:3889:5: note: candidate: 'template<class _IIter, class _Tp> constexpr _IIter std::find(_IIter, _IIter, const _Tp&)'
 3889 |     find(_InputIterator __first, _InputIterator __last,
      |     ^~~~
/usr/include/c++/13/bits/stl_algo.h:3889:5: note:   template argument deduction/substitution failed:
railroad.cpp:16:30: note:   candidate expects 3 arguments, 1 provided
   16 |         return link[x] = find(link[x]);
      |                          ~~~~^~~~~~~~~
In file included from /usr/include/c++/13/algorithm:73:
/usr/include/c++/13/pstl/glue_algorithm_defs.h:60:1: note: candidate: 'template<class _ExecutionPolicy, class _ForwardIterator, class _Tp> __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> std::find(_ExecutionPolicy&&, _ForwardIterator, _ForwardIterator, const _Tp&)'
   60 | find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
/usr/include/c++/13/pstl/glue_algorithm_defs.h:60:1: note:   template argument deduction/substitution failed:
railroad.cpp:16:30: note:   candidate expects 4 arguments, 1 provided
   16 |         return link[x] = find(link[x]);
      |                          ~~~~^~~~~~~~~
In file included from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54:
/usr/include/c++/13/bits/streambuf_iterator.h:435:5: note: candidate: 'template<class _CharT2> typename __gnu_cxx::__enable_if<std::__is_char<_CharT2>::__value, std::istreambuf_iterator<_CharT, std::char_traits<_CharT> > >::__type std::find(istreambuf_iterator<_CharT, char_traits<_CharT> >, istreambuf_iterator<_CharT, char_traits<_CharT> >, const _CharT2&)'
  435 |     find(istreambuf_iterator<_CharT> __first,
      |     ^~~~
/usr/include/c++/13/bits/streambuf_iterator.h:435:5: note:   template argument deduction/substitution failed:
railroad.cpp:16:30: note:   mismatched types 'std::istreambuf_iterator<_CharT, std::char_traits<_CharT> >' and 'int (*)(const char*, const char*) noexcept'
   16 |         return link[x] = find(link[x]);
      |                          ~~~~^~~~~~~~~
railroad.cpp:14:5: note: candidate: 'int find(int)' (near match)
   14 | int find(int x) {
      |     ^~~~
railroad.cpp:14:5: note:   conversion of argument 1 would be ill-formed:
railroad.cpp:16:37: error: invalid conversion from 'int (*)(const char*, const char*) noexcept' to 'int' [-fpermissive]
   16 |         return link[x] = find(link[x]);
      |                               ~~~~~~^
      |                                     |
      |                                     int (*)(const char*, const char*) noexcept
railroad.cpp: In function 'void unite(int, int)':
railroad.cpp:25:15: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   25 |         link[b] = a;
      |               ^
railroad.cpp:25:17: error: assignment of read-only location '*(link + ((sizetype)b))'
   25 |         link[b] = a;
      |         ~~~~~~~~^~~
railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:46:23: warning: pointer to a function used in arithmetic [-Wpointer-arith]
   46 |                 link[i] = i;
      |                       ^
railroad.cpp:46:25: error: assignment of read-only location '*(link + ((sizetype)i))'
   46 |                 link[i] = i;
      |                 ~~~~~~~~^~~
railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~