QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#460579#8686. Zoo ManagementkarunaWA 997ms94308kbC++203.2kb2024-07-01 21:09:272024-07-01 21:09:27

Judging History

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

  • [2024-07-01 21:09:27]
  • 评测
  • 测评结果:WA
  • 用时:997ms
  • 内存:94308kb
  • [2024-07-01 21:09:27]
  • 提交

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());

	map<int, int> mp, mp2;
	for (pii p : V) {
		mp[p.ff]++;
		mp2[p.ss]++;
	}

	if (mp != mp2) {
		cout << "impossible\n";
		exit(0);
	}

	int sum = 0;
	for (auto [x, y] : mp) {
		if (y >= 2) {
			return;
		}

		mp[x] += sum;
		sum += y;
	}

	vector<int> a(n);
	for (int i = n; i > 0; i--) {
		a[i - 1] = --mp[V[i - 1].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 = a[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 (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: 0ms
memory: 3576kb

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: 1ms
memory: 3440kb

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: 3520kb

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: 1ms
memory: 3516kb

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: 3584kb

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: 3512kb

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: 3524kb

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: 0ms
memory: 3440kb

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: 0ms
memory: 3440kb

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: 3656kb

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: 3740kb

input:

1 0
1000000 1000000

output:

possible

result:

ok single line: 'possible'

Test #12:

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

input:

2 0
1000000 987654
987654 1000000

output:

impossible

result:

ok single line: 'impossible'

Test #13:

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

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: 3764kb

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: 28ms
memory: 7016kb

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: 26ms
memory: 7796kb

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: 234ms
memory: 57084kb

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: 420ms
memory: 94308kb

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: 399ms
memory: 93968kb

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: 474ms
memory: 88776kb

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: 997ms
memory: 63776kb

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: 990ms
memory: 63620kb

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: 353ms
memory: 30652kb

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: 478ms
memory: 57564kb

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:

possible

result:

wrong answer 1st lines differ - expected: 'impossible', found: 'possible'