Submission #19357783


Source Code Expand

Copy
/**
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */
#include <bits/stdc++.h>
using namespace std;

const bool ready = [](){
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(12);
    return true;
}();

using ld=long double;
const ld PI = acos((ld)-1);
using ll= long long;
#define int ll
#define all(v) (v).begin(), (v).end()
#define fori(n) for(int i=0; i<int(n); i++)

#define cini(i) int i; cin>>i;
#define cins(s) string s; cin>>s;
#define cind(d) ld d; cin>>d;
#define cinai(a,n) vi a(n); fori(n) { cin>>a[i]; }
#define cinas(s,n) vs s(n); fori(n) { cin>>s[i]; }
#define cinad(a,n) vd a(n); fori(n) { cin>>a[i]; }

using pii= pair<int, int>;
using pdd= pair<ld, ld>;
using vd= vector<ld>;
using vb= vector<bool>;
using vi= vector<int>;
using vvi= vector<vi>;
using vs= vector<string>;

#define endl "\n"

const int INF=1e10+7;
/* lets do bfs from all root towns
 * maintaining the min buy price.
 * Then, foreach relaxation also maintain max ans.
 */
void solve() {
    cini(n);
    cini(m);
    cinai(a,n);
    vvi adj(n);

    for(int i=0; i<m; i++) {
        cini(x);
        cini(y);
        adj[x-1].push_back(y-1);
    }

    vi minBuy(n,INF);   /* minBuy[i] minimum price we have bought when in town i */

    int ans=0;

    function<void(int,int)> dfs=[&](int v, int mi) {
        if(minBuy[v]<=mi)
            return;

        minBuy[v]=mi;
        ans=max(ans, a[v]-minBuy[v]);
        for(int chl : adj[v])
            dfs(chl, min(minBuy[v], a[chl]));

    };

    for(int i=0; i<n; i++) 
        dfs(i, a[i]);

    cout<<ans<<endl;
}

signed main() {
    solve();
}

Submission Info

Submission Time
Task E - Peddler
User spookywooky
Language C++ (GCC 9.2.1)
Score 0
Code Size 1722 Byte
Status WA
Exec Time 113 ms
Memory 32856 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 2
WA × 1
AC × 46
WA × 3
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All extreme_00.txt, extreme_01.txt, extreme_02.txt, extreme_03.txt, handmade_00.txt, handmade_01.txt, random_00.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_dense_00.txt, random_dense_01.txt, random_dense_02.txt, random_dense_03.txt, random_dense_04.txt, random_dense_05.txt, random_dense_06.txt, random_dense_07.txt, random_dense_08.txt, random_dense_09.txt, random_small_00.txt, random_small_01.txt, random_small_02.txt, random_small_03.txt, random_small_04.txt, random_small_05.txt, random_small_06.txt, random_small_07.txt, random_small_08.txt, random_small_09.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
extreme_00.txt AC 113 ms 32856 KB
extreme_01.txt AC 62 ms 12492 KB
extreme_02.txt AC 73 ms 14908 KB
extreme_03.txt AC 33 ms 11004 KB
handmade_00.txt AC 2 ms 3532 KB
handmade_01.txt WA 2 ms 3588 KB
random_00.txt AC 58 ms 12156 KB
random_01.txt AC 96 ms 10976 KB
random_02.txt AC 45 ms 6016 KB
random_03.txt AC 38 ms 7556 KB
random_04.txt AC 43 ms 5400 KB
random_05.txt AC 26 ms 9448 KB
random_06.txt AC 14 ms 4088 KB
random_07.txt AC 49 ms 9600 KB
random_08.txt AC 61 ms 7544 KB
random_09.txt AC 47 ms 11844 KB
random_10.txt AC 33 ms 5744 KB
random_11.txt AC 68 ms 12148 KB
random_12.txt AC 41 ms 8696 KB
random_13.txt AC 68 ms 13164 KB
random_14.txt AC 44 ms 7876 KB
random_15.txt AC 81 ms 12584 KB
random_16.txt AC 44 ms 7924 KB
random_17.txt AC 81 ms 13560 KB
random_18.txt AC 13 ms 4760 KB
random_19.txt AC 48 ms 11824 KB
random_dense_00.txt AC 19 ms 4500 KB
random_dense_01.txt AC 29 ms 5624 KB
random_dense_02.txt AC 35 ms 5144 KB
random_dense_03.txt AC 30 ms 4952 KB
random_dense_04.txt AC 2 ms 3632 KB
random_dense_05.txt AC 17 ms 4100 KB
random_dense_06.txt AC 35 ms 5532 KB
random_dense_07.txt AC 5 ms 3632 KB
random_dense_08.txt AC 37 ms 5728 KB
random_dense_09.txt AC 16 ms 4140 KB
random_small_00.txt AC 2 ms 3492 KB
random_small_01.txt AC 3 ms 3576 KB
random_small_02.txt AC 3 ms 3612 KB
random_small_03.txt WA 7 ms 3524 KB
random_small_04.txt AC 2 ms 3532 KB
random_small_05.txt AC 2 ms 3468 KB
random_small_06.txt AC 3 ms 3612 KB
random_small_07.txt AC 2 ms 3596 KB
random_small_08.txt AC 2 ms 3540 KB
random_small_09.txt AC 3 ms 3600 KB
sample_01.txt AC 2 ms 3468 KB
sample_02.txt AC 2 ms 3544 KB
sample_03.txt WA 2 ms 3528 KB