QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#481154#906. 强连通分量xyloph0nex17#WA 211ms73644kbC++141.8kb2024-07-16 20:54:192024-07-16 20:54:19

Judging History

你现在查看的是最新测评结果

  • [2024-07-16 20:54:19]
  • 评测
  • 测评结果:WA
  • 用时:211ms
  • 内存:73644kb
  • [2024-07-16 20:54:19]
  • 提交

answer

//El Psy Kongroo
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ri int
#define TIME (1e3 * clock() / CLOCKS_PER_SEC)
using namespace std ;
template <typename T>
inline void read(T&x){
	x = 0 ; char c = getchar() ; bool flg = 1 ; while(c > '9' || c < '0'){if(c == '-')flg = 0 ; c = getchar() ;}
	while(c >= '0' && c <= '9'){x = (x << 1) + (x << 3) + (c ^ 48) ; c = getchar() ;} x = flg ? x : -x ;
}
template <typename T,typename ...Args>
inline void read(T&x,Args&...args){read(x),read(args...);}
bool m_bg ;
const int N = 5e5 + 10 ;
struct star{int to,pre ;}e[N*2] ; int head[N<<1],strn=1 ;
struct line{int u,v ;}L[N] ;
void add(int u,int v){e[++strn].to=v,e[strn].pre=head[u],head[u]=strn ;}
int dfn[N],low[N],dfnn,sc[N],scn,stk[N],top ; vector<int>scc[N] ;
void tarjan(int u){
	dfn[u] = low[u] = ++dfnn ; stk[++top] = u ;
	for(ri i = head[u] , v ; i ; i = e[i].pre){
		v=e[i].to ;
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]) ;
		else if(!sc[v])low[u]=min(low[u],dfn[v]) ;
	}
	if(dfn[u]==low[u]){
		sc[u]=++scn ;
		while(top&&stk[top]!=u)scc[scn].pb(stk[top]),sc[stk[top]]=scn,top-- ;
		scc[scn].pb(u),top-- ;
	}
}
int n,m ; vector<int>G[N] ;
queue<int>q ; int d[N] ;
void topo(){
	for(ri i = 1 ; i <= scn ; i++)if(!d[i])q.push(i) ;
	while(!q.empty()){
		int u = q.front() ; q.pop() ; printf("%d ",(int)scc[u].size()) ; for(ri p : scc[u])printf("%d ",p-1) ; printf("\n") ;
		for(ri v : G[u])if(!--d[v])q.push(v) ;
	}
}
bool m_ed ;
signed main(){
	//freopen("a.in","r",stdin) ;
	read(n,m) ; for(ri i = 1 , u , v ; i <= m ; i++)read(u,v),u++,v++,add(u,v),L[i]={u,v} ;
	for(ri i = 1 ; i <= n ; i++)if(!dfn[i])tarjan(i) ;
	printf("%d\n",scn) ;
	for(ri i = 1 , u , v ; i <= m ; i++){
		u = sc[L[i].u] , v = sc[L[i].v] ;
		if(sc[u]!=sc[v])G[u].pb(v),d[v]++ ; 
	}topo() ;
	return 0 ;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 32736kb

input:

6 7
1 4
5 2
3 0
5 5
4 1
0 3
4 2

output:

4
2 3 0 
2 4 1 
1 5 
1 2 

result:

ok OK

Test #2:

score: -100
Wrong Answer
time: 211ms
memory: 73644kb

input:

500000 500000
389812 410922
255712 339244
274009 248522
347288 199231
235313 301629
469588 84917
364188 449407
392348 436920
26220 198288
162188 468965
274222 92196
463222 408478
231663 467768
382681 38083
412497 160479
280851 268689
101149 25450
62271 9177
38892 268598
273853 250782
191939 89247
40...

output:

499590
1 3 
1 4 
1 5 
1 6 
1 7 
1 10 
1 13 
1 14 
1 17 
1 19 
1 20 
1 21 
1 24 
1 25 
1 26 
1 27 
1 31 
1 32 
1 34 
1 37 
1 39 
1 42 
1 43 
1 46 
1 47 
1 59 
1 60 
1 67 
1 68 
1 76 
1 80 
1 85 
1 86 
1 88 
1 89 
1 94 
1 107 
1 111 
1 113 
1 114 
1 119 
1 120 
1 121 
1 123 
1 129 
1 130 
1 132 
1 133...

result:

wrong answer 479301 is later than 80771, but there is an edge (479301, 80771)