QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#481154 | #906. 强连通分量 | xyloph0nex17# | WA | 211ms | 73644kb | C++14 | 1.8kb | 2024-07-16 20:54:19 | 2024-07-16 20:54:19 |
Judging History
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)