记录详情

Time Exceeded

/in/foo.cc: In function 'int dfs(int, int)':
/in/foo.cc:55:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
/in/foo.cc: In function 'int main()':
/in/foo.cc:57:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j;
        ^
# 状态 耗时 内存占用
#1 Accepted 63ms 21.055 MiB
#2 Accepted 124ms 24.0 MiB
#3 Accepted 227ms 24.949 MiB
#4 Accepted 230ms 24.941 MiB
#5 Accepted 234ms 24.941 MiB
#6 Time Exceeded ≥1005ms ≥22.566 MiB

代码

#include<bits/stdc++.h>
#define N 500001
using namespace std;
int n,m,a[N],ans;
int S,P;
int cnt,fir[N];
int dfn[N],low[N];
int num,stac[N],top;
int col,color[N];
int key[N],u[N],v[N];
bool vis[N],l[N],lose[N];
struct ss{
	int po,nx;
}e[N];
void add(int x,int y){
	e[++cnt].nx = fir[x];
	e[cnt].po = y;
	fir[x] = cnt;
}
void tarjan(int x){
	dfn[x] = ++num;
	low[x] = num;
	vis[x] = 1;
	stac[++top] = x;
	for(int i = fir[x]; i ; i = e[i].nx){
		int p = e[i].po;
		if(!dfn[p]){
			tarjan(p);
			low[x] = min(low[x],low[p]);
		}
		else if(vis[p]) low[x] = min(low[x],dfn[p]);
	}
	if(dfn[x] == low[x]){
		vis[x] = false;
		color[x] = ++col;
		if(l[x]) lose[col] = 1;
		key[col] += a[x];
		while(stac[top] != x){
			int now = stac[top];
			color[now] = col;
			if(l[now]) lose[col] = 1;
			key[col] += a[now];
			vis[now] = false;
			top--;
		}
		top--;
	}
}
int dfs(int x,int now){
	if(lose[x]) ans = max(ans,now);
	for(int i = fir[x]; i ; i =e[i].nx){
		int p = e[i].po;
		dfs(p,now + key[p]);
	}
}
int main(){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i = 1; i <= m; i++){
		scanf("%d%d",&u[i],&v[i]);
		add(u[i],v[i]);
	}
	for(i = 1; i <= n; i++) scanf("%d",&a[i]);
	scanf("%d%d",&S,&P);
	for(i = 1; i <= P; i++){
		int x;
		scanf("%d",&x);
		l[x] = 1;
	}
	for(i = 1; i <= n; i++)
	if(!dfn[i]) tarjan(i);
	cnt = 0;
	for(i = 1; i <= n; i++) fir[i] = 0;
	for(i = 1; i <= m; i++){
		int x = color[u[i]],y = color[v[i]];
		if(x == y) continue;
		add(x,y);
	}
	dfs(color[S],key[color[S]]);
	printf("%d",ans);
	return 0;
}

信息

递交者
类型
递交
题目
P1006 hitwh 2019 新生赛 G LFhase 与他的学术文章
语言
C++
递交时间
2020-12-24 21:12:16
评测时间
2020-12-24 21:12:16
评测机
分数
80
总耗时
≥1885ms
峰值内存
≥24.949 MiB