oj.uz

Submission #262493

# Submission time Handle Problem Language Result Execution time Memory
262493 2020-08-13T01:41:42 Z daniel920712 Travelling Merchant (APIO17_merchant) C++14
12 / 100
 34 ms 11384 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 11384 KB Output is correct
2 Correct 8 ms 10496 KB Output is correct
3 Correct 7 ms 10496 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10240 KB Output is correct
6 Correct 8 ms 10112 KB Output is correct
7 Correct 9 ms 10240 KB Output is correct
8 Correct 6 ms 9728 KB Output is correct
9 Correct 7 ms 10112 KB Output is correct
10 Correct 8 ms 10112 KB Output is correct
11 Correct 7 ms 10112 KB Output is correct
12 Correct 6 ms 9856 KB Output is correct
13 Correct 8 ms 10240 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 10752 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 10112 KB Output isn't correct
2 Halted 0 ms 0 KB -