oj.uz

Submission #200594

# Submission time Handle Problem Language Result Execution time Memory
200594 2020-02-07T13:38:04 Z Rakhmand Travelling Merchant (APIO17_merchant) C++14
33 / 100
 81 ms 2296 KB 
//
//  ROIGold.cpp
//  Main calisma
//
//  Created by Rakhman on 05/02/2019.
//  Copyright © 2019 Rakhman. All rights reserved.
//
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <iterator>

#define ios ios_base::sync_with_stdio(0), cout.tie(0), cin.tie(0);
#define S second
#define F first
#define pb push_back
#define nl '\n'
#define NL cout << '\n';
#define EX exit(0)
#define all(s) s.begin(), s.end()
#define FOR(i, start, finish, k) for(int i = start; i <= finish; i += k)

const int MXN = 1e5 + 10;
const long long MNN = 1e6 + 200;
const long long MOD = 1e9 + 7;
const long long INF = 1e18;
const int OO = 1e9 + 10;

typedef long long llong;
typedef unsigned long long ullong;

using namespace std;

void istxt(bool yes){
    if(yes == 1){
        freopen("balancing.in", "r", stdin);
        freopen("balancing.out", "w", stdout);
    }else{
        freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
    }
}

int n, m, k;
llong b[110][1100], s[110][1100], ans[110][110], u[MXN], v[MXN], cost[MXN];
llong g[110][110];
llong mx[110][110];

bool check(int ans){
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            g[i][j] = INF;
        }
    }
    for(int i = 1; i <= m; i++){
        g[u[i]][v[i]] = ans * cost[i] - mx[u[i]][v[i]];
    }
    
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(g[i][i] <= 0){
            return true;
        }
    }
    return false;
}

int main () {
    ios;
    //istxt(0);
    cin >> n >> m >> k;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            cin >> b[i][j] >> s[i][j];
        }
    }
    for(int i = 1; i <= m; i++){
        cin >> u[i] >> v[i] >> cost[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= k; j++){
            if(b[i][j] != -1){
                for(int nx = 1; nx <= n; nx++){
                    if(s[nx][j] != -1){
                        //cout << i << ' ' << nx << ' ' << j << nl;
                        //cout << (s[nx][j] - b[i][j]) / g[i][nx] << ' '<< b[i][j] << ' ' << s[nx][j] << ' ' << g[i][nx]<< nl;
                        mx[i][nx] = max(mx[i][nx], s[nx][j] - b[i][j]);
                    }
                }
            }
        }
    }
    llong l = 0, r = 1e9;
    while(r - l > 1){
        llong  m = (r + l) / 2;
        if(check(m)){
            l = m;
        }else{
            r = m;
        }
    }
    cout << (check(r) ? r : l);
}

Compilation message

merchant.cpp: In function 'void istxt(bool)':
merchant.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.in", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("balancing.out", "w", stdout);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
merchant.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
         freopen("/Users/rakhmanabdirashov/Desktop/folder/Programming/Road2Master/Road2Master/input.txt", "r", stdin);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2168 KB Output is correct
2 Correct 42 ms 1272 KB Output is correct
3 Correct 43 ms 1272 KB Output is correct
4 Incorrect 10 ms 760 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

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

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 1656 KB Output is correct
2 Correct 81 ms 2296 KB Output is correct
3 Correct 44 ms 1400 KB Output is correct
4 Correct 47 ms 1528 KB Output is correct
5 Correct 47 ms 1528 KB Output is correct
6 Correct 44 ms 1404 KB Output is correct
7 Correct 15 ms 1016 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 11 ms 888 KB Output is correct
10 Correct 11 ms 888 KB Output is correct
11 Correct 11 ms 888 KB Output is correct
12 Correct 11 ms 888 KB Output is correct
13 Correct 10 ms 888 KB Output is correct

Subtask #4
0 / 34.0

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