QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#44617#906. 强连通分量CCPSDCGK#WA 9ms28816kbC++232.3kb2022-08-20 12:57:502022-08-20 12:57:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-20 12:57:51]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:28816kb
  • [2022-08-20 12:57:50]
  • 提交

answer

#include<map>
#include<set>
#include<queue>
#include<deque>
#include<cmath>
#include<ctime>
#include<bitset>
#include<vector>
#include<cstdio>
#include<string>
#include<random>
#include<cassert>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
using ll=long long;
using uint=unsigned int;
using ull=unsigned long long;
#define endl '\n'
#define lb lower_bound
#define ub upper_bound
#define eb emplace_back
#define fs fflush(stdout)
#define ump unordered_map
#define pq priority_queue
#define clz __builtin_clz
#define ctz __builtin_ctz
#define sz(x) (int)x.size()
#define np next_permutation
#define clzl __builtin_clzll
#define ctzl __builtin_ctzll
#define ppc __builtin_popcount
#define all(x) x.begin(),x.end()
#define ppcl __builtin_popcountll
#define fpi(x) freopen(x,"r",stdin)
#define fpo(x) freopen(x,"w",stdout)
#define uid uniform_int_distribution
#define urd uniform_real_distribution
#define me(x,y) memset(x,y,sizeof(x))
#define dbg(x) cerr<<"In Line "<<__LINE__<<' '<<#x<<'='<<(x)<<'\n'
#define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,iosiz,stdin),p1==p2)?EOF:*p1++
#define iosiz 1024
char buf[iosiz],*p1=buf,*p2=buf;
template<class T> inline T &re(T &x){
	x=0;int f=1;char ch=gc;
	while(ch<48||ch>57){
		if(ch==45) f=-f;ch=gc;
	}
	while(ch>47&&ch<58) x=(x<<1)+(x<<3)+(ch^48),ch=gc;
	return x*=f;
}
#define mod 998244353
#define inf 0x3f3f3f3f
int cnt,dfn[500005],tim,low[500005],s[500005],scc[500005],top;
bool is[500005];
vector<int> v[500005],edge[500005];
void dfs(int u){
    dfn[u]=low[u]=++tim,is[s[++top]=u]=1;
    for(int v:edge[u]){
        if(!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);
        else if(is[v]) low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        cnt++;
        do{
            scc[s[top]]=cnt,is[s[top]]=0;
        }while(s[top--]^u);
    }
}
int main(){
	#ifdef CCPSDCGK
	fpi("shuju.txt");
	#endif
    int n=re(n),m=re(m);
    while(m--){
        int u=re(u),v=re(v);
        edge[u].eb(v);
    }
    for(int i=0;i<n;i++) if(!dfn[i]) dfs(i);
    for(int i=0;i<n;i++) v[scc[i]].eb(i);
    cout<<cnt<<endl;
    for(int i=1;i<=cnt;i++){
        cout<<sz(v[i])<<' ';
        for(int pos:v[i]) cout<<pos<<' ';cout<<endl;
    }
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 9ms
memory: 28816kb

input:

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

output:

4
2 0 3 
1 2 
2 1 4 
1 5 

result:

wrong answer 5 is later than 2, but there is an edge (5, 2)