Submission #19354642


Source Code Expand

Copy
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ppb pop_back
#define endl "\n"
#define vll vector<ll>
#define pll pair<ll,ll>
#define pqb priority_queue<ll>
#define pqs priority_queue<ll,vll,greater<ll> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define sz(x)             (int)((x).size())
#define FAST ios_base :: sync_with_stdio (false); cin.tie (NULL)
#define fo(i,s,n) for(ll i=s;i<n;i++)
#define rfo(i,n,s) for(ll i=n;i>=s;i--)
using namespace std;
typedef int ll;
vll w;
vector<vll> adj;
vector<pll> ans;
vll vis;
ll dfs(ll cur,ll par){
    ll mx=INT_MIN;
    vis[cur]=1;
    for(ll nb:adj[cur]){
        if(nb!=par){
           mx=max(dfs(nb,cur),mx) ;
        }
    }
    if(mx==INT_MIN){
        return ans[cur].fi;
    }
    ans[cur].se=mx;
     return max(mx,w[cur]);
}

int main(){
    FAST;
ll n,m; cin>>n>>m;
w.resize(n+1);
fo(i,1,n+1)cin>>w[i];
adj.resize(n+1);
while(m--){
    ll u,v; cin>>u>>v;
    adj[u].pb(v);
}
ans.resize(n+1);
vis.resize(n+1);
fo(i,1,n+1){
    ans[i].fi=w[i];
}
fo(i,1,n+1){
    if(adj[i].size()==0)continue;
    if(!vis[i])dfs(i,-1);
}
ll res=INT_MIN;
// fo(i,1,n+1){cout<<ans[i].fi<<" "<<ans[i].se<<endl;}
fo(i,1,n+1){
    if(ans[i].se==0)continue;
    res=max(ans[i].se-ans[i].fi,res);
}

 cout<<res;



}

Submission Info

Submission Time
Task E - Peddler
User iamfarraz
Language C++ (GCC 9.2.1)
Score 0
Code Size 1484 Byte
Status TLE
Exec Time 2206 ms
Memory 35832 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 36
TLE × 13
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 35832 KB
extreme_01.txt AC 60 ms 11728 KB
extreme_02.txt TLE 2206 ms 14732 KB
extreme_03.txt AC 34 ms 11028 KB
handmade_00.txt AC 3 ms 3536 KB
handmade_01.txt AC 2 ms 3588 KB
random_00.txt AC 59 ms 12032 KB
random_01.txt AC 73 ms 10724 KB
random_02.txt TLE 2205 ms 4792 KB
random_03.txt AC 34 ms 7604 KB
random_04.txt TLE 2205 ms 4512 KB
random_05.txt AC 31 ms 9416 KB
random_06.txt AC 24 ms 4072 KB
random_07.txt AC 46 ms 9708 KB
random_08.txt AC 467 ms 6664 KB
random_09.txt AC 48 ms 11828 KB
random_10.txt AC 28 ms 5720 KB
random_11.txt AC 69 ms 12072 KB
random_12.txt AC 40 ms 8580 KB
random_13.txt AC 62 ms 12832 KB
random_14.txt AC 45 ms 7676 KB
random_15.txt AC 81 ms 12308 KB
random_16.txt AC 45 ms 7648 KB
random_17.txt AC 81 ms 13672 KB
random_18.txt AC 12 ms 4820 KB
random_19.txt AC 50 ms 11828 KB
random_dense_00.txt TLE 2205 ms 3896 KB
random_dense_01.txt TLE 2205 ms 4484 KB
random_dense_02.txt TLE 2205 ms 4364 KB
random_dense_03.txt TLE 2205 ms 4196 KB
random_dense_04.txt TLE 2205 ms 3296 KB
random_dense_05.txt TLE 2205 ms 3732 KB
random_dense_06.txt TLE 2205 ms 4520 KB
random_dense_07.txt TLE 2205 ms 3360 KB
random_dense_08.txt TLE 2205 ms 4700 KB
random_dense_09.txt TLE 2205 ms 3684 KB
random_small_00.txt AC 7 ms 3532 KB
random_small_01.txt AC 2 ms 3596 KB
random_small_02.txt AC 2 ms 3536 KB
random_small_03.txt AC 2 ms 3488 KB
random_small_04.txt AC 2 ms 3580 KB
random_small_05.txt AC 2 ms 3528 KB
random_small_06.txt AC 2 ms 3592 KB
random_small_07.txt AC 2 ms 3592 KB
random_small_08.txt AC 2 ms 3540 KB
random_small_09.txt AC 3 ms 3540 KB
sample_01.txt AC 4 ms 3532 KB
sample_02.txt AC 3 ms 3592 KB
sample_03.txt AC 2 ms 3520 KB