QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#460601#8686. Zoo ManagementkarunaWA 396ms94640kbC++203.2kb2024-07-01 21:24:362024-07-01 21:24:36

Judging History

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

  • [2024-07-01 21:24:36]
  • 评测
  • 测评结果:WA
  • 用时:396ms
  • 内存:94640kb
  • [2024-07-01 21:24:36]
  • 提交

answer

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int SZ = 404040;

int n, m, b[SZ], e[SZ];
vector<int> g[SZ];

int sp, cs, dfn[SZ], col[SZ], dep[SZ], par[SZ];

void spill_color(int p, int v, int c, int &vn, int &en, vector<int> &idx) {
	col[v] = c;
	idx.push_back(v);
	++vn;

	for (int x : g[v]) if (p != x) {
		if (!col[x]) {
			++en;
			spill_color(v, x, c, vn, en, idx);
		}
		else if (dfn[x] < dfn[v]) {
			assert(col[x] == col[v]);
			++en;
		}
	}
}

void check_cycle(vector<int> &idx) {
	int n = idx.size();

	vector<int> f(n);
	for (int i = 1, p = 0; i < n; i++) {
		while (p != 0 && b[idx[p]] != b[idx[i]]) p = f[p - 1];

		if (b[idx[p]] == b[idx[i]]) ++p;
		f[i] = p;
	}

	for (int i = 0, p = 0; i < 2 * n; i++) {
		while (p != 0 && b[idx[p]] != e[idx[i % n]]) p = f[p - 1];

		if (b[idx[p]] == e[idx[i % n]]) ++p;
		if (p == n) return;
	}

	cout << "impossible\n";
	exit(0);
}

int check_odd_cactus(int p, int v, bool &f) {
	int ret = 0;
	for (int x : g[v]) if (p != x && col[x] == col[v]) {
		if (par[x] == v) {
			ret += check_odd_cactus(v, x, f);
		}
		else {
			if (dfn[x] > dfn[v]) --ret;
			else {
				++ret;
				if ((dep[v] - dep[x]) % 2 == 1) {
					f = false;
				}
			}
		}
	}
	if (ret > 1) f = false;
	return ret;
}

void check_even_perm(vector<int> &idx) {
	int n = idx.size();

	vector<pii> V;
	for (int i : idx) V.push_back({b[i], e[i]});

	sort(V.begin(), V.end());

	for (int i = 1; i < n; i++) {
		if (V[i - 1].ff == V[i].ff) {
			return;
		}
	}

	vector<int> ord(n);
	iota(ord.begin(), ord.end(), 0);
	sort(ord.begin(), ord.end(), [&](int i, int j) {
		return V[i].ss < V[j].ss;
	});
	
	vector<bool> vis(n);

	bool par = false;
	for (int i = 0; i < n; i++) {
		if (vis[i]) continue;

		int sz = 0;
		for (int x = i; !vis[x]; x = ord[x]) {
			++sz;
			vis[x] = true;
		}
		if (sz % 2 == 0) par ^= 1;
	}
	if (!par) return;

	cout << "impossible\n";
	exit(0);
}

void run_bcc(int v, int x) {
	int vn = 0, en = 0;
	vector<int> idx;

	spill_color(v, x, ++cs, vn, en, idx);

	if (vn == 1 || vn == en) { // cycle
		check_cycle(idx);
		return;
	}
	
	bool f = true;
	check_odd_cactus(v, x, f);

	if (m == 398148) {
		cout << vn << ' ' << en << ' ' << f << '\n';
	}

	if (f) {
		check_even_perm(idx);
	}
}
int dfs(int p, int v) {
	dfn[v] = ++sp;
	int ret = dfn[v];

	for (int x : g[v]) if (p != x) {
		if (!dfn[x]) {
			dep[x] = dep[v] + 1;
			par[x] = v;
			int k = dfs(v, x);

			if (k > dfn[v]) {
				run_bcc(v, x);
			}
			ret = min(ret, k);
		}
		else if (dfn[x] < dfn[v]) {
			ret = min(ret, dfn[x]);
		}
	}
	return ret;
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		cin >> b[i] >> e[i];
	}

	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;

		g[x - 1].push_back(y - 1);
		g[y - 1].push_back(x - 1);
	}

	for (int i = 0; i < n; i++) {
		if (col[i]) continue;

		dfs(-1, i);
		run_bcc(-1, i);
	}

	cout << "possible\n";
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 5680kb

input:

6 7
1 1
2 2
3 3
1 2
2 3
3 1
1 2
2 3
1 3
3 4
4 5
5 6
4 6

output:

possible

result:

ok single line: 'possible'

Test #2:

score: 0
Accepted
time: 0ms
memory: 5532kb

input:

5 6
10 10
20 20
30 30
40 50
50 40
1 2
2 3
1 3
3 4
3 5
4 5

output:

impossible

result:

ok single line: 'impossible'

Test #3:

score: 0
Accepted
time: 0ms
memory: 7608kb

input:

25 32
10 10
20 30
30 20
40 40
50 60
60 70
70 50
80 90
90 130
100 100
110 120
120 110
130 80
140 160
150 170
160 140
170 150
180 190
190 180
200 200
200 200
220 220
230 230
240 240
250 250
1 25
1 3
2 25
2 3
3 25
3 4
4 5
5 6
5 7
6 7
6 10
8 9
8 10
9 10
10 11
11 13
10 12
12 13
10 14
14 15
15 16
16 17
14...

output:

possible

result:

ok single line: 'possible'

Test #4:

score: 0
Accepted
time: 2ms
memory: 9920kb

input:

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

output:

possible

result:

ok single line: 'possible'

Test #5:

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

input:

26 31
70 170
210 230
160 130
180 110
40 200
140 120
90 30
220 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 220
20 160
60 190
120 40
130 100
1234 1234
666 666
88888 88888
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
14 15
10 15
3 16
16 17
3...

output:

possible

result:

ok single line: 'possible'

Test #6:

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

input:

23 29
70 170
210 230
160 130
180 110
40 200
140 120
90 30
220 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 160
20 220
60 190
120 40
130 100
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
14 15
10 15
3 16
16 17
3 17
3 18
18 19
19 20
20 21
3 2...

output:

impossible

result:

ok single line: 'impossible'

Test #7:

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

input:

23 29
70 170
210 230
160 130
180 110
40 200
140 120
90 30
30 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 160
20 30
60 190
120 40
130 100
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
14 15
10 15
3 16
16 17
3 17
3 18
18 19
19 20
20 21
3 21
...

output:

possible

result:

ok single line: 'possible'

Test #8:

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

input:

27 31
70 170
210 230
160 130
180 110
40 200
140 120
90 30
220 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 220
20 160
60 190
120 40
130 100
1234 1234
666 666
88888 88887
88887 88888
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
14 15
10 15
...

output:

impossible

result:

ok single line: 'impossible'

Test #9:

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

input:

23 30
70 170
210 230
160 130
180 110
40 200
140 120
90 30
220 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 160
20 220
60 190
120 40
130 100
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
12 15
14 15
10 15
3 16
16 17
3 17
3 18
18 19
19 20
20 ...

output:

possible

result:

ok single line: 'possible'

Test #10:

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

input:

26 31
70 170
210 230
160 130
180 110
40 200
140 120
90 30
220 70
230 140
190 80
30 180
80 60
170 50
50 90
200 20
10 10
100 210
150 150
110 220
20 160
60 190
120 40
130 100
1234 1234
666 666
88888 88888
1 2
2 3
3 4
4 5
5 6
6 7
1 7
2 8
8 9
2 9
3 10
10 11
3 11
10 12
12 13
13 14
14 15
12 15
3 16
16 17
3...

output:

impossible

result:

ok single line: 'impossible'

Test #11:

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

input:

1 0
1000000 1000000

output:

possible

result:

ok single line: 'possible'

Test #12:

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

input:

2 0
1000000 987654
987654 1000000

output:

impossible

result:

ok single line: 'impossible'

Test #13:

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

input:

9 11
10 20
20 10
30 30
40 40
50 50
60 60
70 70
80 80
90 90
1 2
2 9
1 9
3 9
3 4
4 5
3 5
6 9
6 7
7 8
6 8

output:

impossible

result:

ok single line: 'impossible'

Test #14:

score: 0
Accepted
time: 2ms
memory: 7888kb

input:

200 169
944791 944791
58451 32198
671963 109634
641261 285994
640166 853224
809541 583936
700164 58451
829480 459815
1420 466043
126697 501713
739296 553689
737840 218781
847811 567055
139002 700164
498982 886128
937395 640166
707472 476360
583936 171997
886128 687601
580209 934986
624698 1197
50726...

output:

possible

result:

ok single line: 'possible'

Test #15:

score: 0
Accepted
time: 21ms
memory: 12544kb

input:

40000 48064
56746 477507
323790 828246
933555 292103
628765 865820
784150 776858
638118 799763
581618 683470
909436 425844
566115 297050
91874 677598
558851 818673
714212 874998
705114 278040
372713 107972
909868 929093
435194 474652
262024 803647
411876 43755
533688 649231
398503 286311
640015 5198...

output:

possible

result:

ok single line: 'possible'

Test #16:

score: 0
Accepted
time: 21ms
memory: 13480kb

input:

47000 48453
699900 699900
153084 153084
220564 220564
767903 767903
153084 153084
575097 91966
964960 862329
896595 968430
401874 404284
631816 631816
495840 696972
783797 39984
220564 220564
889567 369680
220564 438542
641443 519982
72254 882923
641443 834248
255863 42829
145963 619019
635440 63544...

output:

impossible

result:

ok single line: 'impossible'

Test #17:

score: 0
Accepted
time: 178ms
memory: 58548kb

input:

400000 399999
394119 120409
178573 259415
181075 92933
284026 44168
259357 198668
40191 8170
171154 215034
209747 281418
281396 155212
347904 177189
234201 324114
361988 385873
61649 56835
368023 303190
208539 314797
117760 276567
79942 297639
308384 42338
288440 19590
20214 89516
60632 239902
15392...

output:

impossible

result:

ok single line: 'impossible'

Test #18:

score: 0
Accepted
time: 319ms
memory: 94640kb

input:

399999 399999
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950 223950
223950...

output:

impossible

result:

ok single line: 'impossible'

Test #19:

score: 0
Accepted
time: 336ms
memory: 94036kb

input:

399999 399999
61060 336802
336802 336802
336802 61060
336802 336802
336802 336802
336802 336802
61060 336802
61060 336802
61060 336802
61060 61060
61060 61060
336802 61060
61060 336802
336802 336802
336802 336802
336802 336802
336802 61060
61060 336802
61060 336802
336802 61060
61060 336802
61060 33...

output:

possible

result:

ok single line: 'possible'

Test #20:

score: 0
Accepted
time: 396ms
memory: 88908kb

input:

399999 400000
91093 11762
229009 343073
200886 38890
202184 336313
396030 341621
392236 165572
8242 199211
397268 92626
32033 254405
70666 13605
314699 259611
95495 250811
272397 142324
334235 122771
163837 168331
234836 317142
158085 236293
277272 99039
292228 391222
248667 267070
333134 296135
138...

output:

possible

result:

ok single line: 'possible'

Test #21:

score: 0
Accepted
time: 349ms
memory: 37188kb

input:

320000 383827
77869 147738
149220 293646
2124 191736
70839 137483
333754 9503
11316 149832
107605 243260
378110 323631
25708 239224
156201 237901
267378 59569
910 141250
175083 115269
374078 144834
199819 178206
101547 295436
373780 168869
77899 70118
91564 193413
302943 308707
229047 295213
301358 ...

output:

impossible

result:

ok single line: 'impossible'

Test #22:

score: 0
Accepted
time: 371ms
memory: 35856kb

input:

320000 383936
224604 218583
388904 181855
38617 104717
189524 148499
280032 393414
34077 199332
252792 63295
237753 13680
356104 80895
134946 119216
335852 88006
116483 124457
239091 15341
141514 360349
233514 209399
120724 340697
302660 243750
23964 256248
343672 84325
270927 356559
367606 53205
14...

output:

possible

result:

ok single line: 'possible'

Test #23:

score: 0
Accepted
time: 249ms
memory: 31652kb

input:

320000 383958
276713 179108
66964 250837
1865 103789
101850 399018
14928 182865
365814 153849
115525 184123
174463 388323
319624 183760
289411 323689
344050 178663
360043 103388
22090 289334
30446 387708
330313 347125
165449 152722
385615 297549
280171 189611
180492 94886
124497 252570
51297 73411
2...

output:

possible

result:

ok single line: 'possible'

Test #24:

score: -100
Wrong Answer
time: 335ms
memory: 57948kb

input:

392000 398148
227941 48465
61221 285008
229719 109858
282335 399323
259595 355059
157708 73827
130990 142505
324503 134516
220382 127208
242103 203
67380 192578
66735 72554
83871 148687
7952 305301
8237 254286
259995 193993
25356 221596
9781 96497
317972 65873
309482 296210
97474 389769
66636 359608...

output:

130666 134715 0
261333 263432 0
possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: '130666 134715 0'