QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#94734#2341. Dead-End DetectorDaiRuiChen007AC ✓851ms98264kbC++142.6kb2023-04-07 17:19:302023-04-07 17:19:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-07 17:19:31]
  • 评测
  • 测评结果:AC
  • 用时:851ms
  • 内存:98264kb
  • [2023-04-07 17:19:30]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+1;
bool cut[MAXN],vis[MAXN];
int dfn[MAXN],low[MAXN],dcnt;
int siz[MAXN],col[MAXN],cnt[MAXN],all[MAXN];
int u[MAXN],v[MAXN];
struct node {
	int u,v,id;
	node(int _u=0,int _v=0,int _id=0): u(_u),v(_v),id(_id) {}
};
vector <node> G[MAXN],E[MAXN],ans;
inline void tarjan(int p,int fa) {
	dfn[p]=low[p]=++dcnt;
	for(auto e:G[p]) {
		if(e.v==fa) continue;
		if(!dfn[e.v]) {
			tarjan(e.v,p);
			low[p]=min(low[p],low[e.v]);
			if(low[e.v]>dfn[p]) cut[e.id]=true;
		} else low[p]=min(low[p],dfn[e.v]);
	}
}
signed main() {
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		::u[i]=u,::v[i]=v;
		G[u].push_back(node(u,v,i));
		G[v].push_back(node(v,u,i));
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) tarjan(i,0);
	int tot=0;
	for(int i=1;i<=n;++i) {
		if(col[i]) continue;
		++tot;
		auto dfs=[&](auto self,int p) -> void {
			col[p]=tot,++siz[tot];
			for(auto e:G[p]) if(!cut[e.id]&&!col[e.v]) self(self,e.v);
		};
		dfs(dfs,i);
	}
	for(int u=1;u<=n;++u) {
		for(auto e:G[u]) {
			if(!cut[e.id]) continue;
			E[col[e.u]].push_back(node(col[e.u],col[e.v],e.id));
			E[col[e.v]].push_back(node(col[e.v],col[e.u],e.id));
			cut[e.id]=false;
		}
	}
	for(int i=1;i<=tot;++i) {
		if(vis[i]) continue;
		int rt=0;
		auto init=[&](auto self,int p,int fa) -> void {
			cnt[p]=(siz[p]==1)?1:0,all[p]=1,vis[p]=true;
			if(siz[p]>1) rt=p;
			for(auto e:E[p]) {
				if(e.v!=fa) {
					self(self,e.v,p);
					cnt[p]+=cnt[e.v];
					all[p]+=all[e.v];
				}
			}
		};
		init(init,i,0);
		if(rt) {
			init(init,rt,0);
			auto dfs=[&](auto self,int p,int fa) -> void {
				for(auto e:E[p]) {
					if(e.v==fa) continue;
					if(cnt[e.v]==all[e.v]) {
						int x=e.id;
						if(col[u[x]]==p) ans.push_back(node(u[x],v[x],0));
						else ans.push_back(node(v[x],u[x],0));
					} else self(self,e.v,p);
				}
			};
			dfs(dfs,rt,0);	
		} else {
			auto dfs=[&](auto self,int p,int fa) -> void {
				for(auto e:E[p]) {
					if(e.v==fa) continue;
					if(E[p].size()==1) {
						int x=e.id;
						if(col[u[x]]==p) ans.push_back(node(u[x],v[x],0));
						else ans.push_back(node(v[x],u[x],0));
					}
					if(E[e.v].size()==1) {
						int x=e.id;
						if(col[u[x]]==p) ans.push_back(node(v[x],u[x],0));
						else ans.push_back(node(u[x],v[x],0));
					}
					self(self,e.v,p);
				}
			};
			dfs(dfs,i,0);
		}
	}
	printf("%d\n",(int)ans.size());
	sort(ans.begin(),ans.end(),[&](node A,node B) {
		if(A.u==B.u) return A.v<B.v;
		return A.u<B.u;
	});
	for(auto e:ans) printf("%d %d\n",e.u,e.v);
	return 0;
}

Details

Test #1:

score: 100
Accepted
time: 5ms
memory: 34864kb

Test #2:

score: 0
Accepted
time: 3ms
memory: 36600kb

Test #3:

score: 0
Accepted
time: 372ms
memory: 74672kb

Test #4:

score: 0
Accepted
time: 2ms
memory: 33892kb

Test #5:

score: 0
Accepted
time: 3ms
memory: 34764kb

Test #6:

score: 0
Accepted
time: 1ms
memory: 37432kb

Test #7:

score: 0
Accepted
time: 1ms
memory: 36392kb

Test #8:

score: 0
Accepted
time: 18ms
memory: 41024kb

Test #9:

score: 0
Accepted
time: 4ms
memory: 35620kb

Test #10:

score: 0
Accepted
time: 6ms
memory: 36260kb

Test #11:

score: 0
Accepted
time: 0ms
memory: 36952kb

Test #12:

score: 0
Accepted
time: 1ms
memory: 34756kb

Test #13:

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

Test #14:

score: 0
Accepted
time: 108ms
memory: 48168kb

Test #15:

score: 0
Accepted
time: 834ms
memory: 95556kb

Test #16:

score: 0
Accepted
time: 443ms
memory: 92600kb

Test #17:

score: 0
Accepted
time: 494ms
memory: 97304kb

Test #18:

score: 0
Accepted
time: 463ms
memory: 96468kb

Test #19:

score: 0
Accepted
time: 0ms
memory: 36232kb

Test #20:

score: 0
Accepted
time: 1ms
memory: 36432kb

Test #21:

score: 0
Accepted
time: 10ms
memory: 35096kb

Test #22:

score: 0
Accepted
time: 140ms
memory: 46684kb

Test #23:

score: 0
Accepted
time: 851ms
memory: 93284kb

Test #24:

score: 0
Accepted
time: 179ms
memory: 98264kb

Test #25:

score: 0
Accepted
time: 797ms
memory: 97116kb

Test #26:

score: 0
Accepted
time: 168ms
memory: 74416kb

Test #27:

score: 0
Accepted
time: 478ms
memory: 76104kb

Test #28:

score: 0
Accepted
time: 465ms
memory: 75620kb

Test #29:

score: 0
Accepted
time: 443ms
memory: 74312kb

Test #30:

score: 0
Accepted
time: 177ms
memory: 80280kb

Test #31:

score: 0
Accepted
time: 392ms
memory: 81388kb

Test #32:

score: 0
Accepted
time: 213ms
memory: 95508kb

Test #33:

score: 0
Accepted
time: 397ms
memory: 95288kb

Test #34:

score: 0
Accepted
time: 799ms
memory: 93280kb

Test #35:

score: 0
Accepted
time: 734ms
memory: 88532kb

Test #36:

score: 0
Accepted
time: 807ms
memory: 91136kb

Test #37:

score: 0
Accepted
time: 821ms
memory: 94020kb

Test #38:

score: 0
Accepted
time: 754ms
memory: 88532kb

Test #39:

score: 0
Accepted
time: 649ms
memory: 84024kb

Test #40:

score: 0
Accepted
time: 537ms
memory: 74800kb

Test #41:

score: 0
Accepted
time: 699ms
memory: 86232kb

Test #42:

score: 0
Accepted
time: 551ms
memory: 73840kb

Test #43:

score: 0
Accepted
time: 594ms
memory: 72352kb

Test #44:

score: 0
Accepted
time: 469ms
memory: 95196kb

Test #45:

score: 0
Accepted
time: 380ms
memory: 95304kb