第三个测试点毒瘤啊!WA 94pts on #3
查看原帖
第三个测试点毒瘤啊!WA 94pts on #3
1073995
Saint_ying_xtf楼主2024/6/19 21:10
// Author: Expert_Dream
// Copyright (c) 2024 Expert_Dream All rights reserved.
// Problem: P3627 [APIO2009] 抢掠计划
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3627
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Date: 2024-06-19 18:59:21

// #pragma GCC optimize(2,3,"Ofast","inline")
#include<bits/stdc++.h>
// #include <atcoder/all>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define x0 _x0_
#define y1 _y1_
#define endl '\n'
#define re register
#define pb push_back
#define vi vector<int>
#define pq priority_queue
#define mem(a,x) memset((a),(x),sizeof(a))
#define debug(x) cout<<"debug:"<<x<<endl;
#define sz(s) (int)(s.size())
#define all(a) a.begin(),a.end()
#define rd(l,r) (myrand()%(r-l+1)+l)
#define print(x) {cout<<x<<endl;return;}
#define For(x,y,z) for(int x = y;x <= z;x++)
#define For_(x,y,z) for(int x = y;x >= z;x--)
#define between(x, flo, top) (flo <= x && x <= top)
// #define double long double
using namespace std;
// using namespace atcoder;
mt19937 myrand(time(0));
template <typename Type> void get_min(Type &w1,const Type w2) { if(w2<w1) w1=w2; } 
template <typename Type> void get_max(Type &w1,const Type w2) { if(w2>w1) w1=w2; }
template <typename Type> Type up_div(Type w1,Type w2) { return (w1/w2+(w1%w2?1:0)); }//向上取整
template <typename Type> Type gcd(Type a,Type b) {int i=__builtin_ctz(a),j=__builtin_ctz(b),x=i>j?j:i,y;b>>=j;while(a){a>>=i;y=b-a;i=__builtin_ctz(y);b=a<b?a:b;a=y<0?-y:y;}return b<<x;}
template <typename Type> Type lcm(Type a,Type b) {return a/gcd(a,b)*b;}
template <typename Type> Type ksm(Type a,Type b) {int res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;}
template <typename Type> Type ksm(Type a,Type b,Type mod) {int res=1;while(b){if(b&1) res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res%mod;}
namespace FastIO {template <typename T = int>inline T read() {T s=0,w=1;char c=getchar();while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}while(isdigit(c))s=(s<<1)+(s<<3)+(c^48),c=getchar();return s*w;}template <typename T>inline void read(T &s){s=0;int w=1;char c=getchar();while(!isdigit(c)){if(c=='-')w=-1;c=getchar();}while(isdigit(c))s=(s<<1)+(s<<3)+(c^48),c=getchar();s*=w;}template <typename T, typename... Args> inline void read(T &x, Args &...args) {read(x), read(args...);}template <typename T>inline void write(T x,char ch = '\n') {if(x<0)x=-x,putchar('-');static char stk[200];int top=0;do{stk[top++]=x%10+'0',x/=10;}while(x);while(top)putchar(stk[--top]);putchar(ch);return;}template <typename T, typename... Args> inline void write(T x, Args ...args) {write(x,' '), write(args...);}template <typename Type> void Write(vector<Type> v) {for(auto it:v)write(it,' ');puts("");}}
using namespace FastIO;
#define int long long
const int mod = 998244353,inf = 0x3f3f3f3f,N = 5e5+5,M = 1e6+5,K = 3000+5;// 1000000007
const long long linf = 0x3f3f3f3f3f3f3f3f;
int n,m;
vi mp[N];
int a[N];
int mx[N];
namespace Tarjan_Scc{
	int dfn[N],low[N],instk[N],dfncnt,scc[N],sc,siz[N];
	stack<int> st;
	void tarjan(int x){
		dfn[x]=low[x]=++dfncnt,instk[x]=1;
		st.push(x);
		for(auto it:mp[x]){
			if(!dfn[it]){
				tarjan(it),low[x]=min(low[x],low[it]);
			}else if(instk[it]) low[x]=min(low[x],dfn[it]);
		}if(dfn[x]==low[x]){
			sc++;
			while(st.top()!=x){
				siz[sc]++,scc[st.top()]=sc;
				mx[sc] += a[st.top()];
				instk[st.top()]=0,st.pop();
			}siz[sc]++,scc[x]=sc;
			mx[sc] += a[st.top()];
			instk[x]=0,st.pop();
		}
	}
}using namespace Tarjan_Scc;
int s,p;
int J[N];
vi g[N];
int d[N];
int sum[N];
int vis[N];
void solve(){
	cin >> n >> m;
	For(i,1,m) {
		int u,v; cin >> u >> v;
		mp[u].pb(v);
	}
	For(i,1,n )cin>> a[i];
	cin >> s >> p;
	For(i,1,p) cin >> J[i];
	For(i,1,n) if(!dfn[i]) tarjan(i);
	For(i,1,n) for(auto it:mp[i]) if(scc[i]!=scc[it]) g[scc[i]].pb(scc[it]),d[scc[it]]++;
	queue<int> q;q.push(scc[s]);
	For(i,1,sc) if(!d[i])q.push(i);
	sum[scc[s]]=mx[scc[s]];
	For(i,1,sc) if(!d[i] && scc[s] != i) sum[i]=-linf;
	while(sz(q)){
		int f=q.front();q.pop();
		// cout<<f<<endl;
		for(auto it:g[f]){
			d[it]--;
			sum[it]=max(sum[it],sum[f]+mx[it]);
			// debug(sum[it]);
			// cout << f << " " << it << " " << sum[it] << endl;
			if(!d[it]){
				q.push(it);
			}
		}
	}
	// For(i,1,n)cout << scc[i]<<endl;
	// For(i,1,sc)cout<<sum[i]<<endl;
	int ans = 0;
	For(i,1,p){
		get_max(ans,sum[scc[J[i]]]);
	}cout<<ans;
}signed main(){
	// freopen("std.in","r",stdin);
	// freopen("std.out","w",stdout);
	// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
	// read(T);
	For(_,1,T) solve();
	return 0;
}

/*
4 38
2 8
1 1
3 5

*/
2024/6/19 21:10
加载中...