Submission #19358632


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] != -1e14){
			ans = max(ans,values[i]-arr[i]);
		}
	}
	cout << ans << "\n";
}

Submission Info

Submission Time
Task E - Peddler
User nskybytskyi
Language C++ (GCC 9.2.1)
Score 500
Code Size 993 Byte
Status AC
Exec Time 101 ms
Memory 29776 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 49
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 101 ms 29776 KB
extreme_01.txt AC 58 ms 12064 KB
extreme_02.txt AC 63 ms 14860 KB
extreme_03.txt AC 34 ms 11104 KB
handmade_00.txt AC 8 ms 9784 KB
handmade_01.txt AC 11 ms 9692 KB
random_00.txt AC 62 ms 13188 KB
random_01.txt AC 70 ms 13188 KB
random_02.txt AC 39 ms 10992 KB
random_03.txt AC 35 ms 11288 KB
random_04.txt AC 38 ms 10768 KB
random_05.txt AC 33 ms 11076 KB
random_06.txt AC 21 ms 9888 KB
random_07.txt AC 57 ms 12344 KB
random_08.txt AC 59 ms 11824 KB
random_09.txt AC 41 ms 12356 KB
random_10.txt AC 34 ms 10760 KB
random_11.txt AC 65 ms 13416 KB
random_12.txt AC 35 ms 11552 KB
random_13.txt AC 63 ms 13404 KB
random_14.txt AC 43 ms 11516 KB
random_15.txt AC 74 ms 13664 KB
random_16.txt AC 48 ms 11892 KB
random_17.txt AC 73 ms 14200 KB
random_18.txt AC 15 ms 9952 KB
random_19.txt AC 50 ms 12352 KB
random_dense_00.txt AC 23 ms 10164 KB
random_dense_01.txt AC 33 ms 10808 KB
random_dense_02.txt AC 35 ms 10836 KB
random_dense_03.txt AC 32 ms 10504 KB
random_dense_04.txt AC 11 ms 9632 KB
random_dense_05.txt AC 18 ms 9976 KB
random_dense_06.txt AC 42 ms 10760 KB
random_dense_07.txt AC 10 ms 9712 KB
random_dense_08.txt AC 37 ms 11028 KB
random_dense_09.txt AC 23 ms 9952 KB
random_small_00.txt AC 8 ms 9752 KB
random_small_01.txt AC 8 ms 9712 KB
random_small_02.txt AC 11 ms 9756 KB
random_small_03.txt AC 12 ms 9716 KB
random_small_04.txt AC 16 ms 9708 KB
random_small_05.txt AC 8 ms 9752 KB
random_small_06.txt AC 15 ms 9716 KB
random_small_07.txt AC 8 ms 9756 KB
random_small_08.txt AC 11 ms 9692 KB
random_small_09.txt AC 8 ms 9716 KB
sample_01.txt AC 10 ms 9716 KB
sample_02.txt AC 9 ms 9636 KB
sample_03.txt AC 12 ms 9708 KB