QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#126693#999. 边双连通分量1234567890#WA 297ms61380kbC++201.9kb2023-07-18 21:29:232023-07-18 21:29:26

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-18 21:29:26]
  • 评测
  • 测评结果:WA
  • 用时:297ms
  • 内存:61380kb
  • [2023-07-18 21:29:23]
  • 提交

answer

/*
灏忓簾鐗╋紝杩欓兘涓嶄細 /cf
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define inf (ll)1e9
#define pii pair <ll, ll>
#define fr first
#define se second
const ll mod = 1e9 + 7;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 18, stdin), p1 == p2) ? EOF : *p1++)
inline ll read() {
	ll x = 0, f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') f = ((ch == '-') ? -1 : f), ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
	return x * f;
}
inline void write(ll x) {
	if(x < 0) x = -x, putchar('-');
	if(x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}
ll n, m;
vector <pii> G[200005];
ll dfn[200005], low[200005], tot;
ll sta[200005], top;

ll cnt;
vector <ll> V[200005];
map <pii, ll> M;
inline void Tarjan(ll x, ll fa) {
	dfn[x] = low[x] = ++tot;
	sta[++top] = x;
	for(auto y : G[x]) {
		if(y.se == fa) continue;
		if(!dfn[y.fr]) {
			Tarjan(y.fr, y.se);
			if(low[y.fr] >= dfn[x]) {
				if(sta[top] == y.fr && M[mp(x, y.fr)] < 2) continue;
				cnt++, V[cnt].push_back(x), V[cnt].push_back(y.fr);
				while(sta[top] != y.fr) V[cnt].push_back(sta[top--]);
				top--;
			}
			low[x] = min(low[x], low[y.fr]);
		}
		else low[x] = min(low[x], dfn[y.fr]);
	}
}
int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = read(), m = read();
	for(ll i = 1; i <= m; i++) {
		ll u = read() + 1, v = read() + 1;
		G[u].push_back(mp(v, i));
		G[v].push_back(mp(u, i));
		M[mp(u, v)]++, M[mp(v, u)]++;
	}
	for(ll i = 1; i <= n; i++) if(!dfn[i]) Tarjan(i, 0);
	write(cnt), putchar('\n');
	for(ll i = 1; i <= cnt; i++) {
		write((ll)V[i].size()), putchar(' ');
		for(auto j : V[i]) write(j - 1), putchar(' ');
		putchar('\n');
	}
	return 0;
}
/*
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 14456kb

input:

4 5
0 2
0 1
3 0
2 1
2 3

output:

1
4 0 2 3 1 

result:

ok OK

Test #2:

score: 0
Accepted
time: 4ms
memory: 15608kb

input:

13 21
4 5
8 7
12 3
3 10
1 5
10 2
0 0
11 4
2 12
9 1
9 0
7 8
7 6
9 1
8 2
12 10
11 0
8 6
3 2
5 9
4 11

output:

3
6 0 9 11 4 5 1 
4 2 10 12 3 
3 8 7 6 

result:

ok OK

Test #3:

score: 0
Accepted
time: 1ms
memory: 17260kb

input:

2 2
0 1
1 0

output:

1
2 0 1 

result:

ok OK

Test #4:

score: -100
Wrong Answer
time: 297ms
memory: 61380kb

input:

200000 200000
127668 148778
77100 11865
85144 199231
39485 84917
102044 187263
130204 174776
26220 198288
162188 12078
92196 146334
120537 38083
150353 160479
18707 6545
101149 25450
62271 9177
38892 6454
11709 191939
89247 145109
140599 121858
197410 148980
55975 169098
128576 59852
68224 182347
89...

output:

18194
3 49994 114344 83121 
3 38289 68272 166649 
4 149492 142682 38289 165221 
3 27099 102803 12028 
3 197847 114474 27099 
3 150379 189374 104348 
3 21537 150379 92254 
3 84204 82857 140286 
3 93907 108137 89375 
3 164393 197380 68957 
3 80220 67916 59870 
3 98577 80260 147644 
3 145586 120768 855...

result:

wrong answer twice used vertex 38289