Submission #262493

#	Time	Username	Problem	Language	Result	Execution time	Memory
262493		daniel920712	Travelling Merchant (APIO17_merchant)	C++14	12 / 100	34 ms	11384 KiB

merchant

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <utility>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>

using namespace std;
vector < pair < long long , long long > > Next[200005];
vector < pair < long long , long long > > last[200005];
long long S[105][1005];
long long B[105][1005];
long long in[105]={0};
long long out[105]={0};
bool have[105];
priority_queue < pair < long long , long long > , vector < pair < long long , long long > > , greater < pair < long long , long long > > > all;
int main()
{
    long long N,M,K,a,b,c,ans=0,i,j,k;
    scanf("%lld %lld %lld",&N,&M,&K);
    for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
    while(M--)
    {
        scanf("%lld %lld %lld",&a,&b,&c);
        Next[a].push_back(make_pair(b,c));
        last[b].push_back(make_pair(a,c));
    }

    for(i=1;i<=N;i++) have[i]=0;
    all.push(make_pair(0,1));
    while(!all.empty())
    {
        if(have[all.top().second])
        {
            all.pop();
            continue;
        }
        have[all.top().second]=1;
        in[all.top().second]=all.top().first;
        for(auto i:Next[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first));
        all.pop();
    }

    for(i=1;i<=N;i++) have[i]=0;
    all.push(make_pair(0,1));
    while(!all.empty())
    {
        if(have[all.top().second])
        {
            all.pop();
            continue;
        }
        have[all.top().second]=1;
        out[all.top().second]=all.top().first;
        for(auto i:last[all.top().second]) all.push(make_pair(all.top().first+i.second,i.first));
        all.pop();
    }

    for(i=2;i<=N;i++)
    {
        //printf("%lld %lld\n",in[i],out[i]);
        for(j=1;j<=K;j++)
        {
            if(in[i]&&out[i]&&S[i][j]!=-1&&B[1][j]!=-1)
            {
                //printf("%lld %lld %lld %lld\n",i,j,S[i][j],B[1][j]);
                ans=max(ans,(S[i][j]-B[1][j])/(in[i]+out[i]));
            }
        }
    }
    printf("%lld\n",ans);



    return 0;
}

Compilation message (stderr)

merchant.cpp: In function 'int main()':
merchant.cpp:22:37: warning: unused variable 'k' [-Wunused-variable]
   22 |     long long N,M,K,a,b,c,ans=0,i,j,k;
      |                                     ^
merchant.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |     scanf("%lld %lld %lld",&N,&M,&K);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:24:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |     for(i=1;i<=N;i++) for(j=1;j<=K;j++) scanf("%lld %lld",&B[i][j],&S[i][j]);
      |                                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |         scanf("%lld %lld %lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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