oj.uz

답안 #95767

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
95767 2019-02-02T13:36:04 Z Bodo171 여행하는 상인 (APIO17_merchant) C++14
0 / 100
 1000 ms 13924 KB 
#include <iostream>
#include <fstream>
#include <queue>
#include <climits>
#define mp make_pair
using namespace std;
const int nmax=105;
const int kmax=1005;
queue< pair<int,int> > q;
vector<int> v[nmax];
vector<long long> cost[nmax];
long long d[nmax][kmax],prof[nmax][kmax],pret[nmax][kmax];
int viz[nmax][kmax];
int n,k,m,nod,item,nxt,i,j,a,b,c;
long long p,ans;
bool check(long long x)
{
    while(!q.empty()) q.pop();
    q.push({0,0});
    for(int i=0;i<=n;i++)
        for(int j=0;j<=k;j++)
           viz[i][j]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<=k;j++)
          d[i][j]=LLONG_MIN;
    while(!q.empty())
    {
        nod=q.front().first;item=q.front().second;
        q.pop();
        viz[nod][item]++;
        for(int i=0;i<v[nod].size();i++)
        {
            if(d[nod][item]-1LL*x*cost[nod][i]>=d[v[nod][i]][item])
            {
                d[v[nod][i]][item]=d[nod][item]-1LL*x*cost[nod][i];
                q.push(mp(v[nod][i],item));
                viz[v[nod][i]][item]++;
                if(viz[v[nod][i]][item]>=n*(k+1)+1)
                    return 1;
            }
            nxt=v[nod][i];
            if(item)
            {
                if(d[nod][item]+1LL*prof[nxt][item]-1LL*x*cost[nod][i]>=d[nxt][0]&&prof[nxt][item]!=-1)
                {
                    d[nxt][0]=d[nod][item]-1LL*x*cost[nod][i]+1LL*prof[nxt][item];
                    q.push({nxt,0});
                    viz[nxt][0]++;
                    if(viz[nxt][0]>=n*(k+1)+1)
                        return 1;
                }
            }
        }
        if(!item)
        {
            for(int i=1;i<=k;i++)
             if(d[nod][0]-1LL*pret[nod][i]>=d[nod][i]&&pret[nod][i]!=-1)
             {
                 d[nod][i]=d[nod][0]-1LL*pret[nod][i];
                 q.push({nod,i});
                 viz[nod][i]++;
                 if(viz[nod][i]>=n*(k+1)+1)
                    return 1;
             }
        }
    }
    return 0;
}
int main()
{
    //freopen("data.in","r",stdin);
    ios_base::sync_with_stdio(false);
    cin>>n>>m>>k;
    for(i=1;i<=n;i++)
    {
        pret[i][0]=-1,prof[i][0]=-1;
        for(j=1;j<=k;j++)
        {
            cin>>pret[i][j];
            cin>>prof[i][j];
        }
    }
    for(i=1;i<=n;i++)
        v[0].push_back(i),cost[0].push_back(0);
    for(i=1;i<=k;i++)
        pret[0][i]=prof[0][i]=-1;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        v[a].push_back(b);
        cost[a].push_back(c);
    }
    for(p=30;p>=0;p--)
        if(check(ans+(1LL<<p)))
          ans+=(1LL<<p);
    cout<<ans;
    return 0;
}

Compilation message

merchant.cpp: In function 'bool check(long long int)':
merchant.cpp:31:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i=0;i<v[nod].size();i++)
                     ~^~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1077 ms 7340 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1276 KB Output is correct
2 Correct 9 ms 1144 KB Output is correct
3 Correct 154 ms 1144 KB Output is correct
4 Correct 96 ms 1144 KB Output is correct
5 Correct 709 ms 2524 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 5 ms 1144 KB Output is correct
8 Correct 27 ms 1656 KB Output is correct
9 Correct 14 ms 1276 KB Output is correct
10 Correct 94 ms 1400 KB Output is correct
11 Correct 291 ms 6136 KB Output is correct
12 Correct 332 ms 2940 KB Output is correct
13 Correct 18 ms 1144 KB Output is correct
14 Correct 51 ms 1256 KB Output is correct
15 Execution timed out 1061 ms 1996 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1086 ms 13924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 1276 KB Output is correct
2 Correct 9 ms 1144 KB Output is correct
3 Correct 154 ms 1144 KB Output is correct
4 Correct 96 ms 1144 KB Output is correct
5 Correct 709 ms 2524 KB Output is correct
6 Correct 2 ms 508 KB Output is correct
7 Correct 5 ms 1144 KB Output is correct
8 Correct 27 ms 1656 KB Output is correct
9 Correct 14 ms 1276 KB Output is correct
10 Correct 94 ms 1400 KB Output is correct
11 Correct 291 ms 6136 KB Output is correct
12 Correct 332 ms 2940 KB Output is correct
13 Correct 18 ms 1144 KB Output is correct
14 Correct 51 ms 1256 KB Output is correct
15 Execution timed out 1061 ms 1996 KB Time limit exceeded
16 Halted 0 ms 0 KB -