Submission #19482465


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int ll
#define vi vector<int>
#define vb vector<bool>
#define vvb vector<vb >
#define pii pair<int,int>
#define ss second
#define ff first
#define vpii vector<pii>
#define vvi vector<vi >
#define vs vector<string>
#define vvs vector<vs >
#define pqi priority_queue <int>
#define minpqi priority_queue <int, vector<int>, greater<int> >
#define all(x) x.begin(),x.end()
#define mii map<int,int>
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define per1(i,n) for(ll i=n;i>0;i--)
#define repeat(i,start,n) for(ll i=start;i<n;i++)
#define inp(arr,n) ll arr[n];rep(i,n){ cin>>arr[i];}
#define inp1(arr,n) ll arr[n+1];rep1(i,n){ cin>>arr[i];}
#define inp2d(arr,n,m) ll arr[n][m];rep(i,n)rep(j,m)cin>>arr[i][j];
#define inpg(adj,m) rep(i,m){int a,b;cin>>a>>b;adj[a].pb(b);adj[b].pb(a);}
#define print(a,n) for(ll i=0;i<n;i++){ cout<<a[i]<<" ";}
#define print1(a,n) for(ll i=1;i<=n;i++){ cout<<a[i]<<endl;}
#define mod 998244353
#define maxx 1000000000000000000
#define PI 3.141592653589793238462643383279
#define mmax(a,b,c) max(a,max(b,c))
#define mmin(a,b,c) min(a,min(b,c))
#define init(arr,a) memset(arr,a,sizeof(arr))
#define lb lower_bound
#define ub upper_bound
#define er equal_range#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll long long
#define pb push_back
#define mp make_pair
#define endl "\n"
#define int ll
#define vi vector<int>
#define vb vector<bool>
#define vvb vector<vb >
#define pii pair<int,int>
#define ss second
#define ff first
#define vpii vector<pii>
#define vvi vector<vi >
#define vs vector<string>
#define vvs vector<vs >
#define pqi priority_queue <int>
#define minpqi priority_queue <int, vector<int>, greater<int> >
#define all(x) x.begin(),x.end()
#define mii map<int,int>
#define for0(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define per1(i,n) for(ll i=n;i>0;i--)
#define repeat(i,start,n) for(ll i=start;i<n;i++)
#define inp(arr,n) ll arr[n];rep(i,n){ cin>>arr[i];}
#define inp1(arr,n) ll arr[n+1];rep1(i,n){ cin>>arr[i];}
#define inp2d(arr,n,m) ll arr[n][m];rep(i,n)rep(j,m)cin>>arr[i][j];
#define inpg(adj,m) rep(i,m){int a,b;cin>>a>>b;adj[a].pb(b);adj[b].pb(a);}
#define print(a,n) for(ll i=0;i<n;i++){ cout<<a[i]<<" ";}
#define print1(a,n) for(ll i=1;i<=n;i++){ cout<<a[i]<<endl;}
#define mod 998244353
#define maxx 1000000000000000000
#define PI 3.141592653589793238462643383279
#define mmax(a,b,c) max(a,max(b,c))
#define mmin(a,b,c) min(a,min(b,c))
#define init(arr,a) memset(arr,a,sizeof(arr))
#define lb lower_bound
#define ub upper_bound

int n,m;
bool visi[500001];int value[500001];
int a[500001];
vi v[500001];
void dfs(int node)
{
    visi[node]=1;
 value[node]=max(value[node],a[node]);
    for(auto it:v[node])
    {
        if(!visi[it])
        {
            dfs(it);
            value[node]=max(value[node],value[it]);
        }
    }
}
signed main()
{

    cin>>n>>m;

    for1(i,n)cin>>a[i];
    for1(i,m)
    {
        int x,y;
        cin>>x>>y;
        v[x].pb(y);
    }
  for1(i,n)value[i]=-1e18;
    for1(i,n)
    {
        if(!visi[i])
        dfs(i);
    }
    int ans=-1e18;
    for1(i,n)
    {
        for(auto it:v[i])
        {
            ans=max(ans,value[it]-a[i]);
        }
    }
    cout<<ans<<endl;
}

Submission Info

Submission Time
Task E - Peddler
User pksingh290
Language C++ (GCC 9.2.1)
Score 0
Code Size 3906 Byte
Status WA
Exec Time 207 ms
Memory 37148 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 43
WA × 6
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 207 ms 37148 KB
extreme_01.txt AC 143 ms 19936 KB
extreme_02.txt AC 159 ms 22160 KB
extreme_03.txt AC 77 ms 18504 KB
handmade_00.txt AC 17 ms 15168 KB
handmade_01.txt AC 16 ms 15180 KB
random_00.txt AC 122 ms 20152 KB
random_01.txt AC 145 ms 20448 KB
random_02.txt WA 79 ms 17652 KB
random_03.txt AC 69 ms 17584 KB
random_04.txt WA 74 ms 17016 KB
random_05.txt AC 66 ms 17948 KB
random_06.txt AC 26 ms 15568 KB
random_07.txt AC 98 ms 19008 KB
random_08.txt WA 114 ms 18768 KB
random_09.txt AC 101 ms 19512 KB
random_10.txt AC 61 ms 16876 KB
random_11.txt WA 139 ms 20668 KB
random_12.txt AC 81 ms 18180 KB
random_13.txt AC 133 ms 20792 KB
random_14.txt AC 83 ms 18160 KB
random_15.txt AC 157 ms 20992 KB
random_16.txt WA 91 ms 18144 KB
random_17.txt WA 160 ms 21648 KB
random_18.txt AC 32 ms 15756 KB
random_19.txt AC 105 ms 19728 KB
random_dense_00.txt AC 48 ms 16524 KB
random_dense_01.txt AC 69 ms 17484 KB
random_dense_02.txt AC 66 ms 17220 KB
random_dense_03.txt AC 63 ms 16664 KB
random_dense_04.txt AC 14 ms 15204 KB
random_dense_05.txt AC 33 ms 15932 KB
random_dense_06.txt AC 72 ms 17264 KB
random_dense_07.txt AC 20 ms 15344 KB
random_dense_08.txt AC 75 ms 17376 KB
random_dense_09.txt AC 34 ms 15820 KB
random_small_00.txt AC 13 ms 15180 KB
random_small_01.txt AC 16 ms 15232 KB
random_small_02.txt AC 15 ms 15296 KB
random_small_03.txt AC 14 ms 15168 KB
random_small_04.txt AC 15 ms 15012 KB
random_small_05.txt AC 14 ms 15124 KB
random_small_06.txt AC 12 ms 15064 KB
random_small_07.txt AC 14 ms 15296 KB
random_small_08.txt AC 18 ms 15076 KB
random_small_09.txt AC 16 ms 15176 KB
sample_01.txt AC 15 ms 15176 KB
sample_02.txt AC 15 ms 15180 KB
sample_03.txt AC 14 ms 15180 KB