Submission #1160020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160020		jer033	Travelling Merchant (APIO17_merchant)	C++20	0 / 100	116 ms	2388 KiB

merchant

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
const ll NINF = -1'000'000'000'000'000;

vector<ll> dijkstra(int N, int start, vector<vector<pil>> (&roads))
{
    //return a COST array, i.e. all values are NEGATIVE/NONPOSITIVE
    priority_queue<pli, vector<pli>, greater<pli>> pq;
    vector<ll> dist(N, 1);
    pq.push({0, start});
    while (!pq.empty())
    {
        pli nex = pq.top(); pq.pop();
        ll leng = nex.first;
        int node = nex.second;
        if (dist[node] == 1)
        {
            dist[node] = leng;
            for (pil edge: roads[node])
            {
                int neigh = edge.first;
                ll cos = edge.second;
                pq.push({leng-cos, neigh});
            }
        }
    }
    return dist;
}

vector<vector<int>> all_scc(int N, vector<vector<ll>> (&shortest_paths))
{
    vector<bool> done(N, 0);
    vector<vector<int>> ans;
    for (int i=0; i<N; i++)
        if (done[i] == 0)
        {
            vector<int> one_scc;
            for (int j=i; j<N; j++)
            {
                if ((shortest_paths[i][j]!=1ll) and (shortest_paths[j][i]!=1ll))
                {
                    done[j] = 1;
                    one_scc.push_back(j);
                }
                else
                {
                    shortest_paths[i][j] = 1;
                    shortest_paths[j][i] = 1;
                }
            }
            ans.push_back(one_scc);
        }
    return ans; 
}

bool cycle_detector(int N, vector<vector<int>> (&edges))
{
    vector<int> pointing_to(N, 0);
    for (vector<int> edgelist: edges)
        for (int j: edgelist)
        {
            pointing_to[j]++;
            //cout << j << ' ';
        }
    queue<int> bye_bye;
    for (int i=0; i<N; i++)
        if (pointing_to[i] == 0)
            bye_bye.push(i);
    while (!bye_bye.empty())
    {
        int i = bye_bye.front();
        bye_bye.pop();
        for (int j: edges[i])
        {
            pointing_to[j]--;
            if (pointing_to[j]==0)
                bye_bye.push(j);
        }
    }
    for (int i=0; i<N; i++)
        if (pointing_to[i] > 0)
            return 1;
    return 0;
}

bool bellman_ford(int N, vector<vector<ll>> (&profit), vector<vector<ll>> (&shortest_paths), vector<vector<int>> (&sccs), ll efficiency)
{
    vector<vector<int>> best_to_precede(N);
    for (vector<int> scc: sccs)
    {
        int i = scc[0];
        vector<ll> earnings(N, NINF);
        earnings[i] = 0;
        int rounds = scc.size()+1;
        bool improve = 0;
        for (int round = 0; round<rounds; round++)
        {
            improve = 0;
            for (int j: scc)
                for (int k: scc)
                {
                    if (j!=k)
                    {
                        ll new_earnings = earnings[k] + profit[j][k] + efficiency*shortest_paths[j][k];
                        if (earnings[j] <= new_earnings)
                        {
                            if (earnings[j] < new_earnings)
                            {
                                earnings[j] = new_earnings;
                                improve = 1;
                                best_to_precede[j] = {k};
                            }
                            else
                            {
                                best_to_precede[j].push_back(k);
                            }
                        }
                    }
                }
        }
        if (improve)
            return 1;
    }
    return cycle_detector(N, best_to_precede);
}

int main()
{
    int N, M, K;
    cin >> N >> M >> K;
    vector<vector<pll>> goods(N, vector<pll> (K));
    for (int i=0; i<N; i++)
        for (int j=0; j<K; j++)
        {
            ll b, s;
            cin >> b >> s;
            goods[i][j] = {b, s};
        }
    vector<vector<pil>> roads(N);
    for (int i=0; i<M; i++)
    {
        int V, W; ll T;
        cin >> V >> W >> T;
        V--; W--;
        roads[V].push_back({W, T});
    }
    vector<vector<ll>> shortest_paths(N);
    for (int i=0; i<N; i++)
        shortest_paths[i] = dijkstra(N, i, roads);

    vector<vector<ll>> profit(N, vector<ll> (N, 0));
    for (int i=0; i<N; i++)
        for (int j=0; j<N; j++)
        {
            ll bes = 0;
            for (int k=0; k<K; k++)
            {
                if ((goods[i][k].first != -1ll) and (goods[j][k].second !=-1ll))
                    bes = max(bes, goods[j][k].second - goods[i][k].first);
            }
            profit[i][j] = bes;
        }

    vector<vector<int>> sccs = all_scc(N, shortest_paths);
    ll lo = 0;
    ll hi = 1'000'000'001;
    while (lo!=hi)
    {
        ll mid = (lo+hi+1)/2;
        if (bellman_ford(N, profit, shortest_paths, sccs, mid))
            lo = mid;
        else
            hi = mid-1;
    }
    cout << lo << '\n';
}

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