Submission #19361362


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=INT_MIN;

    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 rananjay23
Language C++ (GCC 9.2.1)
Score 0
Code Size 1726 Byte
Status WA
Exec Time 94 ms
Memory 32892 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 94 ms 32892 KB
extreme_01.txt AC 57 ms 12484 KB
extreme_02.txt AC 72 ms 14788 KB
extreme_03.txt AC 32 ms 10964 KB
handmade_00.txt AC 2 ms 3544 KB
handmade_01.txt WA 2 ms 3540 KB
random_00.txt AC 55 ms 12048 KB
random_01.txt AC 66 ms 10932 KB
random_02.txt AC 38 ms 5956 KB
random_03.txt AC 31 ms 7568 KB
random_04.txt AC 36 ms 5424 KB
random_05.txt AC 23 ms 9464 KB
random_06.txt AC 13 ms 4048 KB
random_07.txt AC 44 ms 9624 KB
random_08.txt AC 56 ms 7460 KB
random_09.txt AC 43 ms 11756 KB
random_10.txt AC 28 ms 5716 KB
random_11.txt AC 60 ms 12056 KB
random_12.txt AC 38 ms 8528 KB
random_13.txt AC 59 ms 13108 KB
random_14.txt AC 38 ms 7736 KB
random_15.txt AC 69 ms 12492 KB
random_16.txt AC 43 ms 7776 KB
random_17.txt AC 70 ms 13688 KB
random_18.txt AC 11 ms 4536 KB
random_19.txt AC 49 ms 11788 KB
random_dense_00.txt AC 18 ms 4392 KB
random_dense_01.txt AC 32 ms 5424 KB
random_dense_02.txt AC 30 ms 5128 KB
random_dense_03.txt AC 31 ms 4872 KB
random_dense_04.txt AC 2 ms 3508 KB
random_dense_05.txt AC 15 ms 3904 KB
random_dense_06.txt AC 36 ms 5344 KB
random_dense_07.txt AC 8 ms 3716 KB
random_dense_08.txt AC 38 ms 5716 KB
random_dense_09.txt AC 12 ms 4124 KB
random_small_00.txt AC 3 ms 3432 KB
random_small_01.txt AC 2 ms 3492 KB
random_small_02.txt AC 2 ms 3544 KB
random_small_03.txt WA 2 ms 3520 KB
random_small_04.txt AC 2 ms 3544 KB
random_small_05.txt AC 3 ms 3476 KB
random_small_06.txt AC 1 ms 3548 KB
random_small_07.txt AC 2 ms 3540 KB
random_small_08.txt AC 2 ms 3536 KB
random_small_09.txt AC 2 ms 3500 KB
sample_01.txt AC 2 ms 3552 KB
sample_02.txt AC 2 ms 3484 KB
sample_03.txt WA 2 ms 3428 KB