Submission #19352085


Source Code Expand

Copy
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read()
{
	int x=0,flag=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')
			flag=0;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
    return (flag?x:~(x-1));
}
struct node{
	int to,next;
} edge[200001];
int n,m,cnt,ans=-114514114514114514,head[200001],val[200001],maxx[200001],vis[200001];
void add(int x,int y)
{
	edge[++cnt].to=y;
	edge[cnt].next=head[x];
	head[x]=cnt;
}
void dfs(int x)
{
  	vis[x]=1;
	if(head[x])
		maxx[x]=-114514114514114514;
	for(int i=head[x];i;i=edge[i].next)
	{
      	if(vis[edge[i].to]==0)
			dfs(edge[i].to);
		maxx[x]=max(maxx[x],maxx[edge[i].to]+val[edge[i].to]-val[x]);
	}
}
signed main()
{
	n=read();
	m=read();
	for(int i=1;i<=n;i++)
		val[i]=read();
	while(m--)
	{
		int x=read(),y=read();
		add(x,y);
	}
  	for(int i=1;i<=n;i++)
      	if(vis[i]==0)
			dfs(i);
	for(int i=1;i<=n;i++)
		if(head[i]!=0)
			ans=max(ans,maxx[i]);
  	if(ans==-114514114514114514)
      	ans=0;
  	cout<<ans;
	return 0;
}

Submission Info

Submission Time
Task E - Peddler
User ShmilyTY
Language C++ (GCC 9.2.1)
Score 0
Code Size 1137 Byte
Status WA
Exec Time 55 ms
Memory 25432 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 500
Status
AC × 3
AC × 25
WA × 24
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 WA 55 ms 25432 KB
extreme_01.txt AC 32 ms 9708 KB
extreme_02.txt AC 31 ms 11352 KB
extreme_03.txt AC 23 ms 6732 KB
handmade_00.txt AC 2 ms 3584 KB
handmade_01.txt AC 2 ms 3620 KB
random_00.txt AC 31 ms 10336 KB
random_01.txt WA 38 ms 10044 KB
random_02.txt WA 20 ms 6356 KB
random_03.txt AC 21 ms 7024 KB
random_04.txt WA 17 ms 5804 KB
random_05.txt AC 19 ms 8508 KB
random_06.txt AC 7 ms 4124 KB
random_07.txt AC 28 ms 8544 KB
random_08.txt AC 27 ms 7732 KB
random_09.txt AC 34 ms 10056 KB
random_10.txt WA 14 ms 5716 KB
random_11.txt WA 38 ms 10572 KB
random_12.txt WA 21 ms 7584 KB
random_13.txt WA 35 ms 11160 KB
random_14.txt WA 22 ms 7364 KB
random_15.txt AC 38 ms 11184 KB
random_16.txt WA 21 ms 7492 KB
random_17.txt WA 43 ms 11868 KB
random_18.txt AC 7 ms 4672 KB
random_19.txt AC 33 ms 10128 KB
random_dense_00.txt WA 13 ms 4928 KB
random_dense_01.txt WA 18 ms 6320 KB
random_dense_02.txt WA 18 ms 6200 KB
random_dense_03.txt WA 17 ms 5848 KB
random_dense_04.txt WA 2 ms 3440 KB
random_dense_05.txt WA 7 ms 4424 KB
random_dense_06.txt WA 25 ms 6176 KB
random_dense_07.txt WA 4 ms 3632 KB
random_dense_08.txt WA 24 ms 6588 KB
random_dense_09.txt WA 7 ms 4140 KB
random_small_00.txt AC 2 ms 3448 KB
random_small_01.txt AC 3 ms 3568 KB
random_small_02.txt AC 2 ms 3452 KB
random_small_03.txt AC 2 ms 3476 KB
random_small_04.txt WA 3 ms 3536 KB
random_small_05.txt AC 4 ms 3548 KB
random_small_06.txt AC 3 ms 3396 KB
random_small_07.txt WA 2 ms 3612 KB
random_small_08.txt AC 3 ms 3448 KB
random_small_09.txt WA 2 ms 3616 KB
sample_01.txt AC 3 ms 3408 KB
sample_02.txt AC 3 ms 3604 KB
sample_03.txt AC 2 ms 3476 KB