记录详情

Accepted

/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 Accepted 58ms 26.047 MiB
#2 Accepted 109ms 30.297 MiB
#3 Accepted 213ms 26.438 MiB
#4 Accepted 218ms 26.363 MiB
#5 Accepted 205ms 27.418 MiB
#6 Accepted 144ms 31.129 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]; 
    int head[N], tot, dp[N], du[N];
    bool vis[N];
    
    void build(int from,int to) 
    {
    	++ du[to];
    	edge[++ tot].to = to;
    	edge[tot].nex = head[from];
    	head[from] = tot;
	}
	
	void topsort(int s)
	{
		queue<int>q;
		dp[s] = val[s];q.push(s);
		while(!q.empty())
		{
			int u = q.front();q.pop();
			vis[u] = 1;
			for(int i = head[u];i;i = edge[i].nex)
			{
			    int v = edge[i].to;
				dp[v] = max(dp[v],dp[u] + val[v]);
				-- du[v];
				if(du[v] == 0) q.push(v);
 			} 
		}
		int ans = 0;
		for(int i = 1;i <= n; i++)
		    if(flag[sd[i]] && vis[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 <= m; 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 23:09:19
评测时间
2020-12-17 23:09:19
评测机
分数
100
总耗时
950ms
峰值内存
31.129 MiB