Submission #19357710


Source Code Expand

Copy
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2*1e5+5;
vector<int> adj[N];
bool visited[N];
vector<ll> values(N,-1e14);
ll arr[N];

void dfs(int cur_node){
	visited[cur_node] = true;
	for(int i = 0; i < (int)adj[cur_node].size();++i){
		int next_node = adj[cur_node][i];
		if(!visited[next_node]){
			dfs(next_node);
			values[cur_node] = max(arr[next_node],values[cur_node]);
			values[cur_node] = max(values[cur_node],values[next_node]);
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	for(int i = 1; i <= n;++i){
		cin >> arr[i];
	}
	for(int i = 0; i < m;++i){
		int x,y;
		cin >> x >> y;
		adj[x].push_back(y);
	}
	memset(visited,false,sizeof(visited));
	for(int i = 1; i <= n;++i){
		if(!visited[i]){
			dfs(i);
		}
	}
	ll ans = -1e18;
	for(int i = 1; i <= n;++i){
		if(values[i] != -1){
			ans = max(ans,values[i]-arr[i]);
		}
	}
	cout << ans << "\n";
}

Submission Info

Submission Time
Task E - Peddler
User nmnsharma007
Language C++ (GCC 9.2.1)
Score 0
Code Size 990 Byte
Status WA
Exec Time 136 ms
Memory 30028 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 26
WA × 23
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 136 ms 30028 KB
extreme_01.txt AC 65 ms 11960 KB
extreme_02.txt WA 66 ms 14856 KB
extreme_03.txt AC 36 ms 10992 KB
handmade_00.txt AC 11 ms 9768 KB
handmade_01.txt AC 11 ms 9676 KB
random_00.txt WA 75 ms 13092 KB
random_01.txt WA 85 ms 13148 KB
random_02.txt WA 45 ms 11020 KB
random_03.txt AC 42 ms 11244 KB
random_04.txt WA 39 ms 10752 KB
random_05.txt AC 34 ms 11088 KB
random_06.txt WA 25 ms 10060 KB
random_07.txt WA 56 ms 12412 KB
random_08.txt WA 68 ms 11816 KB
random_09.txt AC 54 ms 12360 KB
random_10.txt AC 36 ms 10784 KB
random_11.txt WA 83 ms 13400 KB
random_12.txt AC 50 ms 11548 KB
random_13.txt AC 73 ms 13496 KB
random_14.txt AC 54 ms 11540 KB
random_15.txt WA 96 ms 13656 KB
random_16.txt WA 58 ms 11816 KB
random_17.txt WA 97 ms 14180 KB
random_18.txt AC 24 ms 9884 KB
random_19.txt AC 55 ms 12360 KB
random_dense_00.txt WA 27 ms 10232 KB
random_dense_01.txt AC 40 ms 10760 KB
random_dense_02.txt WA 30 ms 10760 KB
random_dense_03.txt WA 36 ms 10560 KB
random_dense_04.txt WA 13 ms 9656 KB
random_dense_05.txt WA 23 ms 9940 KB
random_dense_06.txt WA 37 ms 10824 KB
random_dense_07.txt WA 15 ms 9772 KB
random_dense_08.txt WA 33 ms 11088 KB
random_dense_09.txt WA 21 ms 9888 KB
random_small_00.txt AC 11 ms 9716 KB
random_small_01.txt AC 13 ms 9708 KB
random_small_02.txt WA 15 ms 9700 KB
random_small_03.txt AC 9 ms 9704 KB
random_small_04.txt AC 12 ms 9704 KB
random_small_05.txt AC 15 ms 9800 KB
random_small_06.txt AC 11 ms 9724 KB
random_small_07.txt AC 13 ms 9732 KB
random_small_08.txt WA 16 ms 9772 KB
random_small_09.txt AC 10 ms 9724 KB
sample_01.txt AC 10 ms 9692 KB
sample_02.txt AC 11 ms 9712 KB
sample_03.txt AC 10 ms 9768 KB