QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#671025#996. 割点dieselhuangWA 4ms8600kbC++141003b2024-10-24 10:06:122024-10-24 10:06:13

Judging History

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

  • [2024-10-24 10:06:13]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:8600kb
  • [2024-10-24 10:06:12]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m, dfx = 0, cnt = 0, hd[100010], e[1000010][2], dfn[100010], low[100010], ans[100010];
void dfs(int u, int fa){
	dfn[u] = ++dfx; low[u] = u;
	int i, v, x = 0;
	bool fl = false;
	for(i = hd[u]; i > 0; i = e[i][0]){
		v = e[i][1];
		if(dfn[v] == 0){
			dfs(v, u);
			x++;
			low[u] = min(low[u], low[v]);
			if(fa != 0 && low[v] >= dfn[u]) fl = true;
		}else if(v != fa) low[u] = min(low[u], dfn[v]);
	}
	if(fl) ans[++cnt] = u;
	if(fa == 0 && x > 1) ans[++cnt] = u;
}
int main()
{
	int i, u, v;
	scanf("%d%d", &n, &m);
	for(i = 1; i <= n; i++) hd[i] = 0, dfn[i] = 0;
	for(i = 2; i >> 1 <= m; i++){
		scanf("%d%d", &u, &v);
		e[i][0] = hd[u]; e[i][1] = v; hd[u] = i;
		i++;
		e[i][0] = hd[v]; e[i][1] = u; hd[v] = i;
	}
	for(i = 1; i <= n; i++){
		if(dfn[i] == 0) dfs(i, 0);
	}
	sort(ans + 1, ans + cnt + 1);
	printf("%d\n", cnt);
	for(i = 1; i <= cnt; i++) printf("%d ", ans[i]);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 4ms
memory: 8600kb

input:

12783 21968
4933 7832
8238 2739
3628 7841
9169 6390
7850 8797
8120 8710
5306 9807
10166 2063
2666 5157
5015 4651
4790 12586
10366 7137
12440 7218
6330 3670
2735 8492
1968 2750
6237 1112
6578 9221
743 3820
7155 4583
2537 9747
11331 9916
4454 5631
2978 10340
5293 1803
4944 4296
11800 2742
7903 2018
10...

output:

722
13 22 27 35 39 45 47 62 78 144 155 163 166 168 183 192 219 239 248 250 254 285 290 313 347 356 358 376 386 388 408 415 427 446 459 464 477 504 519 538 555 611 619 625 626 639 644 691 694 709 723 731 779 792 798 802 810 858 871 872 881 908 930 933 938 956 964 974 975 984 988 1012 1033 1043 1055 1...

result:

wrong answer 1st numbers differ - expected: '1440', found: '722'