Submission #1131137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131137		belgianbot	Two Currencies (JOI23_currencies)	C++20	0 / 100	1 ms	408 KiB

currencies

#include <bits/stdc++.h>
#define int long long

using namespace std;

vector< vector< int > > ways;
vector< int > path;
vector< bool > processed;
vector< vector< int > > kingdom;
vector< vector< int > > roads;
int destination;
int N;

void explore (int node)
{
	if (node == destination) ways.push_back(path);
	else
	{
		if (processed[node]) return;
		processed[node] = true;
		for (int i(0); i < N - 1; i++) 
		{
			if (kingdom[node][i])
			{
				for (auto x : roads[kingdom[node][i]]) path.push_back(x);
				explore(i);
			}
			for (int j(0); j < (int) (roads[kingdom[node][i]].size()); j++) path.erase(path.end(), path.end() + 1);
		}
	}
	processed[node] = false;
	return;
}

signed main()
{
	int M, Q; cin >> N >> M >> Q;
	kingdom.resize(N, vector< int > (N, -1));
	roads.resize(M, vector< int >(0));
	for (int i(1); i <= N - 1; i++)
	{
		int city1, city2; cin >> city1 >> city2;
		kingdom[city1][city2] = kingdom[city2][city1] = i;
	}
	for (int i(0); i < M; i++)
	{
		int nbRoad, pay; cin >> nbRoad >> pay;
		roads[nbRoad - 1].push_back(pay);
	}
	while (Q--)
	{
		int start, gold, silver;
		cin >> start >> destination >> gold >> silver;
		ways.clear();path.clear();processed.clear();
		path.resize(1, start); processed.resize(N, false);
		explore(start);
		int ans(-1);
		for (auto x : ways)
		{
			int goldLeft(gold);
			int total(0);
			for (int y : x)
			{
				total += y;
			}
			while (total > silver)
			{
				int biggest = *max_element(x.begin(), x.end());
				if (!biggest)
				{
					goldLeft = -1;
					break;
				}
				total -= biggest;
				*max_element(x.begin(), x.end()) = 0;
				goldLeft--;
			}
			ans = max(ans, goldLeft);
		}
		cout << ans << '\n';
	}
	return 0;		
}

Compilation message (stderr)

In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from currencies.cpp:1:
In static member function 'static constexpr _Tp* std::__copy_move<_IsMove, true, std::random_access_iterator_tag>::__copy_m(const _Tp*, const _Tp*, _Tp*) [with _Tp = long long int; bool _IsMove = true]',
    inlined from 'constexpr _OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = true; _II = long long int*; _OI = long long int*]' at /usr/include/c++/11/bits/stl_algobase.h:495:30,
    inlined from 'constexpr _OI std::__copy_move_a1(_II, _II, _OI) [with bool _IsMove = true; _II = long long int*; _OI = long long int*]' at /usr/include/c++/11/bits/stl_algobase.h:522:42,
    inlined from 'constexpr _OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = true; _II = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _OI = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]' at /usr/include/c++/11/bits/stl_algobase.h:529:31,
    inlined from 'constexpr _OI std::move(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >; _OI = __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >]' at /usr/include/c++/11/bits/stl_algobase.h:652:38,
    inlined from 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::_M_erase(std::vector<_Tp, _Alloc>::iterator, std::vector<_Tp, _Alloc>::iterator) [with _Tp = long long int; _Alloc = std::allocator<long long int>]' at /usr/include/c++/11/bits/vector.tcc:190:6,
    inlined from 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(std::vector<_Tp, _Alloc>::const_iterator, std::vector<_Tp, _Alloc>::const_iterator) [with _Tp = long long int; _Alloc = std::allocator<long long int>]' at /usr/include/c++/11/bits/stl_vector.h:1461:17,
    inlined from 'void explore(long long int)' at currencies.cpp:28:78:
/usr/include/c++/11/bits/stl_algobase.h:431:30: warning: 'void* __builtin_memmove(void*, const void*, long unsigned int)' specified size 18446744073709551608 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
  431 |             __builtin_memmove(__result, __first, sizeof(_Tp) * _Num);
      |             ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/stl_algobase.h:67,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from currencies.cpp:1:
/usr/include/c++/11/bits/stl_iterator.h: In function 'void explore(long long int)':
/usr/include/c++/11/bits/stl_iterator.h:1028:9: note: destination object allocated here
 1028 |       : _M_current(__i) { }
      |         ^~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 28
• Subtask 3: 0 / 30
• Subtask 4: 0 / 32