Submission #1167000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1167000		adriannok	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	1095 ms	5696 KiB

merchant

#include <bits/stdc++.h>


#define sooth true
#define untrue false

using namespace std;

const int inf = 1e9 * 2;

int Nbuffer;

struct edge
{
	int u, t;
	edge(int _u, int _t) : u(_u), t(_t) {}
};

int N, M, K;
vector< vector< vector<int64_t> > > market;
vector< vector<edge> > adj;
vector<bool> beheld;

int64_t dfs ( int i, vector<int> &way, int64_t  length, bool cycle = untrue )
{
	int64_t maxv = 0;
	if( cycle )
	{
		for(int i = 0; i < K; ++i)
			for(int j = 0; j < (int)way.size(); ++j)
			{
				if( -1 != market[way[j]][i][1] && -1 != market[0][i][0] )
					maxv = max(
						maxv, 
						(market[way[j]][i][1] - market[0][i][0])/length
						);
			}
	}
	else 
	{
	beheld[i] = sooth;
	for(const edge &ad : adj[i])
		if(!beheld[ad.u] || ad.u == 0)
		{
			way.push_back(ad.u);
			bool c = (ad.u==0? sooth : untrue);
			maxv = max(maxv, dfs(ad.u, way, length+ad.t, c));
		}
	}
	beheld[i] = untrue;
	way.pop_back();
	return maxv;
}

int main(void)
{
	scanf("%d %d %d", &N, &M, &K);
	market.resize(N, vector< vector<int64_t> >(K, vector<int64_t>(2)));
	adj.resize(N);
	beheld.resize(N, untrue);
	for (vector< vector<int64_t> > &vmrkt : market)
		for(vector<int64_t> &mrkt : vmrkt)
			scanf("%lld %lld", &mrkt[0], &mrkt[1]);
	for (int i = 0; i < M; ++i)
	{
		int u, v, t; scanf("%d %d %d", &u, &v, &t);
		adj[u-1].emplace_back(v-1, t);
	}
	
	vector<int> way;

	printf("%lld\n", dfs(0, way, 0));
	return 	0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:63:35: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type*' {aka 'long int*'} [-Wformat=]
   63 |                         scanf("%lld %lld", &mrkt[0], &mrkt[1]);
      |                                ~~~^
      |                                   |
      |                                   long long int*
      |                                %ld
merchant.cpp:63:40: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type '__gnu_cxx::__alloc_traits<std::allocator<long int>, long int>::value_type*' {aka 'long int*'} [-Wformat=]
   63 |                         scanf("%lld %lld", &mrkt[0], &mrkt[1]);
      |                                     ~~~^
      |                                        |
      |                                        long long int*
      |                                     %ld
merchant.cpp:72:20: warning: format '%lld' expects argument of type 'long long int', but argument 2 has type 'int64_t' {aka 'long int'} [-Wformat=]
   72 |         printf("%lld\n", dfs(0, way, 0));
      |                 ~~~^     ~~~~~~~~~~~~~~
      |                    |        |
      |                    |        int64_t {aka long int}
      |                    long long int
      |                 %ld
merchant.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         scanf("%d %d %d", &N, &M, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |                         scanf("%lld %lld", &mrkt[0], &mrkt[1]);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:66:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |                 int u, v, t; scanf("%d %d %d", &u, &v, &t);
      |                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 12
• Subtask 2: 0 / 21
• Subtask 3: 0 / 33
• Subtask 4: 0 / 34