QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#341891#996. 割点Ishy#WA 2ms4760kbC++142.5kb2024-02-29 22:20:242024-02-29 22:20:26

Judging History

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

  • [2024-02-29 22:20:26]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4760kb
  • [2024-02-29 22:20:24]
  • 提交

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 = 2e4 + 5;
const int M = 1e5 + 5;
int n, m;
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 cut[N];
void tarjan(int u)
{
	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);
			chkmn(low[u], low[v]);
			if(dfn[u] <= low[v])
				cut[u] = 1;
		}
		else
			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);
	}
	for(int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i);
	for(int i = 1; i <= n; ++i)
		if(cut[i]) printf("%d\n", i);
	return 0;
}




詳細信息

Test #1:

score: 0
Wrong Answer
time: 2ms
memory: 4760kb

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:

1
13
22
26
27
29
33
35
37
39
45
47
53
56
62
78
91
118
127
132
144
151
155
156
163
166
168
177
181
183
187
192
194
196
205
219
220
223
225
239
248
250
254
256
265
270
285
290
302
313
315
337
338
347
356
358
376
386
388
408
414
415
427
446
459
461
464
477
486
504
513
519
530
538
555
557
571
574
608
61...

result:

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