QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#473771#995. 桥honglan0301#RE 38ms50448kbC++175.8kb2024-07-12 13:59:442024-07-12 13:59:45

Judging History

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

  • [2024-07-12 13:59:45]
  • 评测
  • 测评结果:RE
  • 用时:38ms
  • 内存:50448kb
  • [2024-07-12 13:59:44]
  • 提交

answer

/*
  author: honglan0301
  Sexy_goodier _ xiaoqing
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <queue>
#include <map>
#include <unordered_map>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <bitset>
#include <assert.h>
using namespace std;

//namespace Fread{const int SIZE=1<<20;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return*S++;}}using namespace Fread;namespace Fwrite{const int SIZE=1<<20;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}using namespace Fwrite;
//#define getchar Fread::getchar
//#define putchar Fwrite::putchar

namespace Fastio{struct Reader{template<typename T>Reader&operator>>(T&x){x=0;short f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();x*=f;return*this;}Reader&operator>>(double&x){x=0;double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(long double&x){x=0;long double t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(__float128&x){x=0;__float128 t=0;short f=1,s=0;char c=getchar();while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else{x*=f;return*this;}while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}Reader&operator>>(char&c){c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();return*this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}Reader&operator>>(string&str){str.clear();char c=getchar();while(c==' '||c=='\n'||c=='\r')c=getchar();while(c!=' '&&c!='\n'&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';struct Writer{const int Setprecision=6;typedef int mxdouble;template<typename T>Writer&operator<<(T x){if(x==0){putchar('0');return*this;}if(x<0)putchar('-'),x=-x;static short sta[40];short top=0;while(x>0)sta[++top]=x%10,x/=10;while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(long double x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(long double)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(__float128 x){if(x<0)putchar('-'),x=-x;mxdouble _=x;x-=(__float128)_;static short sta[40];short top=0;while(_>0)sta[++top]=_%10,_/=10;if(top==0)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;putchar('.');for(int i=0;i<Setprecision;i++)x*=10;_=x;while(_>0)sta[++top]=_%10,_/=10;for(int i=0;i<Setprecision-top;i++)putchar('0');while(top>0)putchar(sta[top]+'0'),top--;return*this;}Writer&operator<<(char c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}Writer&operator<<(string str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl//;fflush(stdout)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long
#define ll long long
#define ull unsigned long long
#define mod 998244353
#define G 3
#define Gi 332748118
mt19937 rnd(time(0));
mt19937_64 rndl(time(0));

int n,m,u[500005],v[500005];
vector <pair<int,int>> e[100005];

int dfn[100005],low[100005],cntd,vis[100005],stk[100005],top,cnts,cs[100005],stkb[100005],topb;
vector <int> dn[100005],en[100005];

void dfs(int x,int bh)
{
	dfn[x]=low[x]=++cntd; vis[x]=1; stk[++top]=x;
	for(auto i:e[x])
	{
		if(i.se==bh) continue;
		if(!dfn[i.fi]) 
		{
			stkb[++topb]=i.se,dfs(i.fi,i.se),low[x]=min(low[x],low[i.fi]);
			if(low[i.fi]>=dfn[x])
			{
				cnts++; cs[x]++; dn[cnts].pb(x);
				while(1) {int nr=stk[top--]; cs[nr]++; dn[cnts].pb(nr); if(nr==i.fi) break;}
				while(1) {int nr=stkb[topb--]; en[cnts].pb(nr); if(nr==i.se) break;}
			}
		}
		else if(vis[i.fi]) 
		{
			low[x]=min(low[x],dfn[i.fi]);
			if(dfn[i.fi]<dfn[x]) stkb[++topb]=i.se;
		}
	}
}

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>u[i]>>v[i],e[u[i]].pb(mp(v[i],i)),e[v[i]].pb(mp(u[i],i));
	for(int i=1;i<=n;i++) if(!dfn[i]) dfs(i,-1);
	vector <int> ans;
	for(int i=1;i<=cnts;i++)
	{
		if(dn[i].size()==2&&en[i].size()==1) ans.pb(en[i][0]);
	}
	sort(ans.begin(),ans.end());
	for(auto i:ans) cout<<u[i]<<" "<<v[i]<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 38ms
memory: 50448kb

input:

24942 387166
12556 21443
22404 16376
11073 24296
1535 11968
23745 2818
5073 12731
22550 14761
24118 12008
22695 18979
15118 13639
2080 8721
692 22578
22581 15267
9278 4127
7457 21674
17693 23448
10949 23429
9700 6009
14140 5064
7742 15164
17336 1662
18903 9760
17645 19575
6540 11942
11 4937
15282 10...

output:


result:

ok 0 lines

Test #2:

score: 0
Accepted
time: 13ms
memory: 28196kb

input:

10599 87159
4698 4000
60 4705
1476 5947
7273 1716
8004 3018
10094 1717
3092 3493
2613 9681
5427 3723
2510 6343
10113 6322
9257 634
4996 10197
9918 5582
6348 9561
10536 9777
8133 540
1917 7838
6666 2220
7951 815
2873 977
9397 4991
3529 1395
1426 3874
6379 9098
9504 3437
9076 9134
4321 3879
10252 9390...

output:


result:

ok 0 lines

Test #3:

score: 0
Accepted
time: 19ms
memory: 28748kb

input:

43236 126833
40500 20695
21481 27642
28098 41772
412 7750
5862 39561
21777 22303
7868 21217
31658 34299
18532 10934
21931 31023
42926 15624
40332 18017
12484 8663
21927 7910
12504 17943
4379 10252
3523 21794
18641 1965
18633 25061
14639 10800
35958 1441
35044 20249
31491 38161
5749 4468
13403 8413
3...

output:

1349 20915
38008 17235
41266 10868
19902 3480
40329 42530
19516 26641
43027 24643
2098 41076
6838 38205
33280 34270
29027 35410
20866 26447
35052 27397
33860 1309
35388 534
25757 13594
30628 31979
38444 33887
39751 20313
28554 31809
39630 34623
43195 34069
16150 42137
13811 35147
3120 17275
36681 29...

result:

ok 719 lines

Test #4:

score: -100
Runtime Error

input:

49992 399165
8308 37286
41253 33600
18414 44236
38678 30403
43606 1459
28337 38324
36285 9669
49565 49785
14096 21520
15003 30556
38808 7647
33458 31201
44773 8348
33753 49802
32310 3168
21074 25490
4402 33409
24426 43322
14935 32620
23905 18122
42387 34044
20819 31052
6164 2735
35280 40824
41926 37...

output:


result: