QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340307#995. 桥orz_zWA 478ms60928kbC++141.4kb2024-02-28 20:54:552024-02-28 20:54:57

Judging History

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

  • [2024-02-28 20:54:57]
  • 评测
  • 测评结果:WA
  • 用时:478ms
  • 内存:60928kb
  • [2024-02-28 20:54:55]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
 // #define int long long
#define F(i, l, r) for(int i = (l); i <= (r); ++i)
#define dF(i, r, l) for(int i = (r); i >= (l); --i)

int ri() {
	int x = 0, f = 1;
	char c = getchar();
	while(c < '0' || c > '9') {
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9') {
		x = x* 10 + c - 48;
		c  = getchar();
	} return x * f;
}

const int _ = 5e5 + 5;

int tot = 1, head[_], to[_ << 1], nxt[_ << 1];

void add(int u, int v) {
	to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

int dfn[_], low[_], cnt;

struct node {
	pair<int, int> a;
	int Id;
};
map<pair<int, int>, node > mp;

vector<node> ans;

void tarjan(int u, int Id = 0) {
	dfn[u] = low[u] = ++cnt;
	for(int i = head[u], v = to[i]; i; i = nxt[i], v = to[i]) {
		if(!dfn[v]) {
			tarjan(v, i);
			 low[u] = min(low[u], low[v]);
			 if(low[v] > low[u]) {
			 	ans.push_back(mp[{u, v}]);
			 }
		} else if(i != (Id ^ 1)) {
			low[u] = min(low[u], dfn[v]);
		}
	}
}
signed main() {
	int n = ri(), m = ri();
	F(i, 1, m) {
		int u = ri(), v = ri();
		add(u, v), add(v, u);
		mp[{u, v}] = mp[{v, u}] = (node){make_pair(u, v), i};
	}
	F(i, 1, n) if(!dfn[i]) tarjan(i);
	sort(ans.begin(), ans.end(), [&](node a, node b) { return a.Id < b.Id;});
	for(node v : ans) {
		cout << v.a.first << ' ' << v.a.second << '\n';
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 478ms
memory: 60928kb

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:

15746 21828
7598 23457
14883 19221
12188 3230
7808 23367
15712 21101
9097 23569
13570 11745
11161 3044
2338 15749
22238 21813
23994 19103
19633 1848
19487 19696
18843 5176
6799 19592
23430 23243
13441 17744
8680 20647
17093 20931
14720 5233
13549 7442
19329 24552
2358 12803
20847 16712
11398 47
1400...

result:

wrong output format Extra information in the output file