QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#340851#996. 割点iorit#WA 0ms5268kbC++141.3kb2024-02-29 13:27:292024-02-29 13:27:30

Judging History

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

  • [2024-02-29 13:27:30]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:5268kb
  • [2024-02-29 13:27:29]
  • 提交

answer

#include <bits/stdc++.h>
#define LL long long
#define sl(n) strlen(n)
#define endline puts("")
#define pii pair<int , int>
#define pr_q priority_queue
#define debug puts("DEBUG.")
using namespace std;
const int N = 5e5 + 10;
const int inf = ~0u >> 2;
int n,m;
struct edge
{
	int v,w,nxt;
}e[N << 1];
int hd[N],cnt = 1;
void add(int u , int v)
{
	++cnt,e[cnt].v = v;
	e[cnt].nxt = hd[u],hd[u] = cnt;
}
vector<int> vc;
int dfn[N],dfn_t,low[N];
bool vis[N << 1];
void dfs(int u , int fa)
{
	// cout << u << endl;
	dfn[u] = low[u] = ++dfn_t;
	int son = 0;
	bool fl = 0;
	for(int i = hd[u];i;i = e[i].nxt)
	{
		if(vis[i] )
			continue;
		int v = e[i].v;
		if(dfn[v] )
			low[u] = min(low[u] , dfn[v] );
		else
		{
			++son;
			vis[i] = vis[i ^ 1] = 1;
			dfs(v , u);
			low[u] = min(low[u] , low[v] );
			fl |= low[v] >= dfn[u];
		}
	}
	if(!fa && son > 1)
		vc.push_back(u);
	else if(fa && fl && son >= 2)
		vc.push_back(u);
	// cout << u << " low= " << low[u] << " dfn= " << dfn[u] << endl;
}
int main()
{
	cin >> n >> m;
	for(int i = 1,u,v;i <= m;i++)
	{
		scanf("%d%d" , &u , &v);
		if(u == v)
			continue;
		add(u , v),add(v , u);
	}
	for(int i = 1;i <= n;i++)
		if( !dfn[i] )
			dfs(i , 0);
	sort( vc.begin() , vc.end() );
	cout << vc.size() << endl;
	for(int x : vc)
		printf("%d\n" , x);
	return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 5268kb

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:

1025
13
22
26
35
37
45
47
53
62
91
118
127
132
144
163
168
192
205
219
220
223
225
239
248
250
254
256
285
290
337
347
356
376
386
388
408
414
415
427
446
459
461
464
477
486
504
513
519
538
555
571
611
619
625
626
633
639
644
647
659
691
709
723
731
752
779
781
788
792
798
802
810
871
872
881
900
9...

result:

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