QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341864#995. 桥Ishy#WA 6ms10132kbC++142.6kb2024-02-29 22:05:382024-02-29 22:05:38

Judging History

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

  • [2024-02-29 22:05:38]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:10132kb
  • [2024-02-29 22:05:38]
  • 提交

answer

// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 1000000007
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define PLI pair<LL, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { (a > b) && (a = b); }
template<typename T> void chkmx(T &a, const T b) { (a < b) && (a = b); }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		k >>= 1, Sqr(x);
	}
	return res;
}
template<typename T> void read(T &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 1e5 + 5;
const int M = 5e5 + 5;
int n, m;
PII ed[N];
struct Lexington
{
	int e, ne;	
};
struct Noshiro
{
	int idx = 1, h[N];
	Lexington lxt[M << 1];
	void clear()
	{
		idx = 1;
		memset(h, 0, sizeof(h));
	}
	void add(int x, int y)
	{
		lxt[++idx] = (Lexington){y, h[x]};
		h[x] = idx;
	}
	void adds(int x, int y)
	{
		add(x, y), add(y, x);
	}
}nsr;
int low[N], dfn[N], timestamp;
bool bridge[M];
void tarjan(int u, int from)
{
	low[u] = dfn[u] = ++timestamp;	
	for(int i = nsr.h[u]; i; i = nsr.lxt[i].ne)
	{
		int v = nsr.lxt[i].e;
		if(!dfn[v])
		{
			tarjan(v, i);
			chkmn(low[u], low[v]);
			if(dfn[u] < low[v])
				bridge[i / 2] = 1;
		}
		else if(i != (from ^ 1))
			chkmn(low[u], dfn[v]); 
	}
}
int main()
{
	read(n), read(m);
	for(int i = 1; i <= m; ++i)
	{
		int x, y;
		read(x), read(y);
		nsr.adds(x, y);
		ed[i] = MP(x, y);
	}
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i, 0);
	for(int i = 1; i <= m; ++i)
		if(bridge[i]) printf("%d %d\n", ed[i].fi, ed[i].se);
	return 0;
}




Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 6ms
memory: 10132kb

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:

23086 9796
11649 13969
15710 11305
17825 4536
24043 4070
11329 8017
11641 11818
23345 12685
975 14740
11747 13836
1074 21620
20267 8205
22847 10889
9139 22269

result:

wrong output format Extra information in the output file