CSES - Datatähti 2024 loppu

Submission details
Task:	Polut
Sender:	Niilo
Submission time:	2024-01-21 17:57:05 +0200
Language:	C++ (C++17)
Status:	READY
Result:	33

Feedback
group	verdict	score
#1	ACCEPTED	33
#2	TIME LIMIT EXCEEDED	0
#3	TIME LIMIT EXCEEDED	0

Test results
test	verdict	time	group
#1	ACCEPTED	0.02 s	1, 2, 3	details
#2	ACCEPTED	0.02 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.02 s	1, 2, 3	details
#6	ACCEPTED	0.02 s	1, 2, 3	details
#7	ACCEPTED	0.02 s	1, 2, 3	details
#8	ACCEPTED	0.02 s	1, 2, 3	details
#9	ACCEPTED	0.02 s	1, 2, 3	details
#10	ACCEPTED	0.02 s	1, 2, 3	details
#11	ACCEPTED	0.02 s	1, 2, 3	details
#12	ACCEPTED	0.05 s	2, 3	details
#13	ACCEPTED	0.05 s	2, 3	details
#14	ACCEPTED	0.05 s	2, 3	details
#15	ACCEPTED	0.04 s	2, 3	details
#16	TIME LIMIT EXCEEDED	--	2, 3	details
#17	TIME LIMIT EXCEEDED	--	2, 3	details
#18	ACCEPTED	0.79 s	3	details
#19	TIME LIMIT EXCEEDED	--	3	details
#20	TIME LIMIT EXCEEDED	--	3	details
#21	TIME LIMIT EXCEEDED	--	3	details
#22	TIME LIMIT EXCEEDED	--	3	details
#23	TIME LIMIT EXCEEDED	--	3	details

Code

#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
const int O = 2e5+1;

vector<int> V[O], W[O], T, A, B;
int N, M;
unordered_set<ll> P;
unordered_set<int> R[O];
bool Z[O];

void f(int i) {
	Z[i] = 1;
	for (int j : V[i]) {
		if (!Z[j]) f(j);
	}
	T.push_back(i);
}

bool g(int a, int b) {
	return P.count((ll)a | ((ll)b<<32));
}

int main() {
	cin >> N >> M;
	for (int i=0; i < M; ++i) {
		int a, b;
		cin >> a >> b;
		V[a].push_back(b);
		W[b].push_back(a);
		P.insert((ll)a | ((ll)b<<32));
	}
	for (int i=1; i <= N; ++i) {
		if (!Z[i]) f(i);
	}
	reverse(T.begin(),T.end());
	R[T[0]].insert(0);
	for (int i=1; i < N; ++i) {
		int a = T[i], b = T[i-1];
		if (g(b,a)) {
			for (int d : R[b]) {
				if (b != d) R[a].insert(d);
			}
		}
		if (R[b].count(0)) {
			R[a].insert(b);
		} else {
			for (int c : W[a]) {
				if (R[b].count(c)) {
					R[a].insert(b);
					break;
				}
			}
		}
		if (R[a].empty()) {
			cout << "NO\n";
			return 0;
		}
	}
	cout << "YES\n";
	A.push_back(T[N-1]);
	bool a = 1;
	for (int i=N-2; i >= 0; --i) {
		int j = T[i];
		if (a) {
			if (R[A.back()].count(j) && (B.empty() || g(j,B.back()))) {
				B.push_back(j);
				a = 0;
			} else {
				A.push_back(j);
				a = 1;
			}
		} else {
			if (R[B.back()].count(j) && g(j,A.back())) {
				A.push_back(j);
				a = 1;
			} else {
				B.push_back(j);
				a = 0;
			}
		}
	}
	reverse(A.begin(),A.end());
	cout << A.size() << ' ';
	for (int i : A) cout << i << ' ';
	reverse(B.begin(),B.end());
	cout << '\n' << B.size() << ' ';
	for (int i : B) cout << i << ' ';
	cout << '\n';
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
`2 0` view save

correct output
`YES 1 2 1 1` view save

user output
`YES 1 1 1 2` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`5 8 3 4 2 4 2 5 1 3 ...` view save

correct output
`YES 2 2 5 3 1 3 4` view save

user output
`YES 2 2 5 3 1 3 4` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 300 74 145 156 176 192 168 141 133 ...` view save

correct output
`YES 87 200 136 117 13 169 22 187 1...` view save

user output
`YES 87 200 136 117 13 169 22 187 1...` Truncated

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 37 119 47 10 17 31 130 28 ...` view save

correct output
`YES 90 84 70 170 117 129 17 31 186...` view save

user output
`YES 90 84 70 170 117 129 17 31 186...` Truncated

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 79 1 104 127 31 38 83 85 ...` view save

correct output
`YES 7 70 186 22 171 36 40 135 193 41 91 25 42 160 83 2 173 5...` view save

user output
`YES 193 41 91 25 42 160 83 2 173 5...` Truncated

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 145 50 4 102 136 55 148 34 ...` view save

correct output
`YES 109 70 125 78 128 170 126 184 ...` view save

user output
`YES 112 43 5 126 100 110 175 199 8...` Truncated

Test 7

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 44 38 198 85 69 167 74 39 ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 8

Group: 1, 2, 3

Verdict: ACCEPTED

input
`200 500 41 93 98 4 171 72 127 166 ...` view save

correct output
`YES 88 76 116 195 197 82 42 130 46...` view save

user output
`YES 99 58 136 178 152 15 156 50 17...` Truncated

Test 9

Group: 1, 2, 3

Verdict: ACCEPTED

input
`192 494 17 148 82 57 100 152 38 102 ...` view save

correct output
`YES 154 191 183 77 3 173 83 112 15...` view save

user output
`YES 38 24 108 106 172 2 68 15 40 8...` Truncated

Test 10

Group: 1, 2, 3

Verdict: ACCEPTED

input
`193 497 24 110 17 193 129 117 23 186 ...` view save

correct output
`YES 24 156 123 30 189 95 34 5 96 1...` view save

user output
`YES 24 156 123 30 189 95 34 5 96 1...` Truncated

Test 11

Group: 1, 2, 3

Verdict: ACCEPTED

input
`194 500 57 158 23 40 31 50 189 121 ...` view save

correct output
`YES 27 168 116 136 175 180 12 89 6...` view save

user output
`YES 27 168 116 136 175 180 12 89 6...` Truncated

Test 12

Group: 2, 3

Verdict: ACCEPTED

input
`10000 15000 8243 3033 3299 579 4920 2342 2816 7811 ...` view save

correct output
`YES 9236 3099 5585 9185 7222 9342 ...` view save

user output
`YES 9236 3099 5585 9185 7222 9342 ...` Truncated

Test 13

Group: 2, 3

Verdict: ACCEPTED

input
`10000 20000 6246 3603 5105 3531 6953 4682 2625 3510 ...` view save

correct output
`YES 8734 5847 7473 5388 4872 4557 ...` view save

user output
`YES 1266 1772 8738 2693 6330 5784 ...` Truncated

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`10000 20000 5853 1019 2465 2936 2022 3609 9429 4118 ...` view save

correct output
`YES 5204 3987 6388 4732 4403 7869 ...` view save

user output
`YES 4994 3151 9186 4134 7454 9827 ...` Truncated

Test 15

Group: 2, 3

Verdict: ACCEPTED

input
`10000 20000 3439 3806 9336 5210 7784 848 5162 9830 ...` view save

correct output
`NO` view save

user output
`NO` view save

Test 16

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`10000 20000 8908 287 2525 6024 1851 844 72 6898 ...` view save

correct output
`YES 2487 3806 7839 4969 2661 4199 ...` view save

user output
(empty)

Test 17

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

input
`7621 19995 6223 473 4893 990 5326 3614 421 591 ...` view save

correct output
`YES 6340 5076 2779 1201 7053 1720 ...` view save

user output
(empty)

Test 18

Group: 3

Verdict: ACCEPTED

input
`200000 300000 17151 175317 68698 43101 190738 54240 105443 37722 ...` view save

correct output
`YES 163946 182154 120966 26194 771...` view save

user output
`YES 36054 78937 84140 109692 61016...` Truncated

Test 19

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 500000 128290 197429 67543 48696 156347 40114 114481 197 ...` view save

correct output
`YES 30833 112330 10351 23335 11682...` view save

user output
(empty)

Test 20

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 500000 93623 55553 60858 72598 15531 30650 196624 28459 ...` view save

correct output
`YES 99923 156477 12892 147937 1060...` view save

user output
(empty)

Test 21

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 500000 76457 8199 163450 19462 107840 24269 178642 128924 ...` view save

correct output
`NO` view save

user output
(empty)

Test 22

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`200000 500000 181062 44502 115318 176115 33437 57568 163325 17752 ...` view save

correct output
`YES 141551 129409 52010 108449 242...` view save

user output
(empty)

Test 23

Group: 3

Verdict: TIME LIMIT EXCEEDED

input
`190479 499998 113031 136485 5993 50604 19834 84581 39043 93744 ...` view save

correct output
`YES 170843 113031 163271 166394 43...` view save

user output
(empty)

Datatähti 2024 loppu

Polut

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Tasks

Submissions (Niilo)