Submission #339014

#	Time	Username	Problem	Language	Result	Execution time	Memory
339014		lohacho	Harbingers (CEOI09_harbingers)	C++14	Compilation error	0 ms	0 KiB

This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.

harbingers

#include <bits/stdc++.h>

using namespace std;

using LL = __int128_t;
int N;
vector<vector<LL>> cht((int)1e5, vector<LL>(3));
vector<vector<vector<LL>>> era((int)1e5);
int top, etop;

inline LL getc(vector<LL> A, vector<LL> B){
	return (B[2] - A[2]) / (A[1] - B[1]) + ((B[2] - A[2]) % (A[1] - B[1]) > 0);
}

void push(LL A, LL B){
	cht[top++] = {-(LL)1e18, A, B};
	if(top >= 2){
		cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
	}
	vector<vector<LL>> np;
	if(N < (int)1e5){
		while(top >= 3 && cht[top - 1][0] <= cht[top - 2][0]){
			np.push_back(cht[top - 2]);
			cht[top - 2] = cht[top - 1]; --top;
			cht[top - 1][0] = getc(cht[top - 2], cht[top - 1]);
		}
	}
	era[etop++] = np;
}

LL get(LL x){
	vector<LL> vc = {x + 1, -(LL)1e18, -(LL)1e18};
	int pos = lower_bound(cht.begin(), cht.begin() + top, vc) - cht.begin() - 1;
	return cht[pos][1] * x + cht[pos][2];
}

void del(){
	--top;
	vector<vector<LL>> now = era[--etop];
	for(int i = (int)now.size() - 1; i >= 0; --i){
		cht[top++] = now[i];
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	vector<vector<pair<int, int>>> way(N);
	for(int i = 0; i < N - 1; ++i){
		int a, b, c; cin >> a >> b >> c; --a; --b;
		way[a].push_back({b, c}), way[b].push_back({a, c});
	}
	vector<pair<int, int>> val(N);
	for(int i = 1; i < N; ++i){
		cin >> val[i].first >> val[i].second;
	}
	vector<LL> sum(N), chk(N), dp(N);
	function<void(int, int)> dfs = [&](int x, int dis){
		chk[x] = 1;
		sum[x] = dis;
		if(x){
			dp[x] = get(val[x].second) + val[x].first + val[x].second * sum[x];
		}
		else dp[x] = 0;
		push(-sum[x], dp[x]);
		for(auto&nxt:way[x]){
			if(!chk[nxt.first]){
				dfs(nxt.first, dis + nxt.second);
			}
		}
		del();
	};
	dfs(0, 0);
	for(int i = 1; i < N; ++i){
		cout << dp[i] << ' ';
	}
	return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:76:8: error: ambiguous overload for 'operator<<' (operand types are 'std::ostream' {aka 'std::basic_ostream<char>'} and '__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type' {aka '__int128'})
   76 |   cout << dp[i] << ' ';
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/9/ostream:166:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  166 |       operator<<(long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:170:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  170 |       operator<<(unsigned long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:174:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  174 |       operator<<(bool __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/9/ostream:702,
                 from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/9/bits/ostream.tcc:91:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]'
   91 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/9/ostream:181:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  181 |       operator<<(unsigned short __n)
      |       ^~~~~~~~
In file included from /usr/include/c++/9/ostream:702,
                 from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/9/bits/ostream.tcc:105:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]'
  105 |     basic_ostream<_CharT, _Traits>::
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/9/istream:39,
                 from /usr/include/c++/9/sstream:38,
                 from /usr/include/c++/9/complex:45,
                 from /usr/include/c++/9/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:54,
                 from harbingers.cpp:1:
/usr/include/c++/9/ostream:192:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  192 |       operator<<(unsigned int __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:201:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  201 |       operator<<(long long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:205:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  205 |       operator<<(unsigned long long __n)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:220:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  220 |       operator<<(double __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:224:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  224 |       operator<<(float __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:232:7: note: candidate: 'std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]'
  232 |       operator<<(long double __f)
      |       ^~~~~~~~
/usr/include/c++/9/ostream:511:5: note: candidate: 'std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]'
  511 |     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:517:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]'
  517 |     operator<<(basic_ostream<char, _Traits>& __out, char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:523:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]'
  523 |     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
      |     ^~~~~~~~
/usr/include/c++/9/ostream:528:5: note: candidate: 'std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]'
  528 |     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
      |     ^~~~~~~~