51NOD - 1815调查任务

显然答案就是路径上的次大值。因为点可以一直走，所以可以缩成DAG。

然后在上面dp。

要注意，因为是路径上面的两点，所以不能来自同一路径。

比如:1->2,2->4,1->3,3->4, 4不能同时继承2,3的答案。

AC代码：

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
const int N=4e5+10;
int n,m,q,st,a[N],dfn[N],low[N],scc[N],vis[N],cnt,co,mx1[N],mx2[N],deg[N],mx3[N],mx4[N];
vector<int> g[N],v[N];	stack<int> s;
void Tarjan(int x){dfn[x]=low[x]=++cnt; s.push(x),vis[x]=1;for(auto to:g[x]){if(!dfn[to]) Tarjan(to),low[x]=min(low[x],low[to]);else if(vis[to]) low[x]=min(low[x],dfn[to]);}if(dfn[x]==low[x]){int u;	co++;do{u=s.top(); s.pop(); vis[u]=0; scc[u]=co;if(a[u]>mx1[co]) mx2[co]=mx1[co],mx1[co]=a[u];else if(a[u]>mx2[co]&&a[u]!=mx1[co]) mx2[co]=a[u];mx3[co]=mx1[co],mx4[co]=mx2[co];}while(u!=x);}
}
void dfs(int x){vis[x]=1;for(auto to:v[x]){deg[to]++;	if(!vis[to])	dfs(to);}
}
void Top(){queue<int> q;	q.push(scc[st]);while(q.size()){int u=q.front();	q.pop();for(auto to:v[u]){if(--deg[to]==0)	q.push(to);mx2[to]=max(mx2[to],mx2[u]);if(mx1[to]!=mx3[u]) mx2[to]=max(mx2[to],min(mx1[to],mx3[u]));else mx2[to]=max(mx2[to],mx4[u]);			if(mx3[u]>mx3[to]) mx4[to]=mx3[to],mx3[to]=mx3[u];else if(mx3[to]>mx3[u]&&mx3[u]>mx4[to]) mx4[to]=mx3[u];if(mx4[u]>mx3[to]) mx4[to]=mx3[to],mx3[to]=mx4[u];else if(mx3[to]>mx4[u]&&mx4[u]>mx4[to]) mx4[to]=mx4[u];}}
}
signed main(){cin>>n>>m>>q>>st;for(int i=1;i<=n;i++)	scanf("%d",&a[i]);for(int i=1,x,y;i<=m;i++)	scanf("%d %d",&x,&y),g[x].push_back(y);for(int i=1;i<=n;i++)	if(!dfn[i])	Tarjan(i);for(int i=1;i<=n;i++)	for(auto to:g[i])	if(scc[i]!=scc[to])v[scc[i]].push_back(scc[to]);dfs(scc[st]);	Top();for(int i=1,x;i<=q;i++){scanf("%d",&x);if(!vis[scc[x]]){printf("-1 ");	continue;}printf("%d ",mx2[scc[x]]);}return 0;
}