记录详情

Wrong Answer

/in/foo.cc: In function 'void work1::tarjan(int)':
/in/foo.cc:44:23: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
    while(y = st[top --])
                       ^
# 状态 耗时 内存占用
#1 Wrong Answer 62ms 29.922 MiB
#2 Accepted 112ms 28.297 MiB
#3 Accepted 234ms 26.039 MiB
#4 Accepted 232ms 25.398 MiB
#5 Accepted 207ms 27.812 MiB
#6 Wrong Answer 155ms 29.531 MiB

代码

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5e5 + 101;
int s, p;
struct node{
	int from, to;
}E[N];
int val[N], sd[N], flag[N]; 
int n, m;
namespace work1
{
	struct Edge{
     	int to, nex;
    }edge[N]; 
    int tot, cnt, dfn[N], low[N];
    int st[N], top, head[N];
    bool vis[N];
    
    void build(int from,int to) 
    {
    	edge[++ tot].to = to;
    	edge[tot].nex = head[from];
    	head[from] = tot;
	}
	
	void tarjan(int u)
	{
		low[u] = dfn[u] = ++ cnt;
		st[++ top] = u;vis[u] = 1;
		for(int i = head[u];i;i = edge[i].nex)
		{
			int v = edge[i].to;
			if(!dfn[v])
			{
				tarjan(v);
				low[u] = min(low[u],low[v]); 
			}
			else if(vis[v]) low[u] = min(dfn[v],low[u]);
		}
		if(dfn[u] == low[u])
		{
			int y;
			while(y = st[top --])
			{
				sd[y] = u;
				vis[y] = 0;
				flag[u] = flag[u] | flag[y];
				if(y == u) break;
				val[u] += val[y];
 			}
		}
	}
}

namespace work2
{
	struct Edge{
     	int to, nex;
    }edge[N]; 
    struct node{
    	int u, val;
    	bool operator < (const node &a) const{
		    return val < a.val;
		}
	};
    int head[N], tot, dp[N];
    bool vis[N];
    
    void build(int from,int to) 
    {
    	edge[++ tot].to = to;
    	edge[tot].nex = head[from];
    	head[from] = tot;
	}
	
	void topsort(int s)
	{
		priority_queue<node>q;
		dp[s] = val[s];q.push((node){s,dp[s]});
		while(!q.empty())
		{
			int u = q.top().u;q.pop();
			if(vis[u]) continue;
			vis[u] = 1;
			for(int i = head[u];i;i = edge[i].nex)
			{
				int v = edge[i].to;
				if(dp[v] < dp[u] + val[v])
				{
					dp[v] = dp[u] + val[v];
					q.push((node) {v,dp[v]});
				}
			} 
		}
		int ans = 0;
		for(int i = 1;i <= n; i++)
		    if(flag[sd[i]]) ans = max(ans,dp[sd[i]]);//cout << dp[sd[i]] << endl;
		cout << ans << endl;
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m; i++)
	{
		int u, v;scanf("%d%d",&u,&v);
		work1::build(u,v);
		E[i].from = u;E[i].to = v;
	}
	for(int i = 1;i <= n; i++) scanf("%d",&val[i]);
	scanf("%d%d",&s,&p);
	for(int i = 1;i <= p; i++)
	{
		int x; scanf("%d",&x);flag[x] = 1;
	}
	for(int i = 1;i <= n; i++)
	    if(!(work1::dfn[i])) work1::tarjan(i); 
	for(int i = 1;i <= n; i++)
	{
		int u = E[i].from, v = E[i].to;
		if(sd[u] != sd[v]) work2::build(sd[u],sd[v]);
	}
	work2::topsort(sd[s]);
}

信息

递交者
类型
递交
题目
P1006 hitwh 2019 新生赛 G LFhase 与他的学术文章
语言
C++
递交时间
2020-12-17 22:50:37
评测时间
2020-12-17 22:50:37
评测机
分数
70
总耗时
1005ms
峰值内存
29.922 MiB