CSES - BOI 2026 Mirror Day 1

Submission details
Task:	Tourist's Journey
Sender:	frederikvase
Submission time:	2026-04-16 13:56:21 +0300
Language:	C++ (C++20)
Status:	READY
Result:	100

Feedback
subtask	verdict	score
#1	ACCEPTED	7
#2	ACCEPTED	8
#3	ACCEPTED	11
#4	ACCEPTED	29
#5	ACCEPTED	15
#6	ACCEPTED	30

Test results
test	verdict	time	subtask
#1	ACCEPTED	0.00 s	1, 2, 5, 6	details
#2	ACCEPTED	0.00 s	1, 2, 3, 4, 5, 6	details
#3	ACCEPTED	0.00 s	1, 2, 3, 4, 5, 6	details
#4	ACCEPTED	0.00 s	1, 2, 4, 5, 6	details
#5	ACCEPTED	0.00 s	1, 2, 4, 5, 6	details
#6	ACCEPTED	0.00 s	1, 2, 3, 4, 5, 6	details
#7	ACCEPTED	0.00 s	1, 2, 5, 6	details
#8	ACCEPTED	0.00 s	1, 2, 5, 6	details
#9	ACCEPTED	0.00 s	1, 2, 5, 6	details
#10	ACCEPTED	0.00 s	2, 3, 4, 5, 6	details
#11	ACCEPTED	0.00 s	2, 5, 6	details
#12	ACCEPTED	0.00 s	2, 5, 6	details
#13	ACCEPTED	0.01 s	2, 5, 6	details
#14	ACCEPTED	0.23 s	3, 4, 6	details
#15	ACCEPTED	0.23 s	3, 4, 6	details
#16	ACCEPTED	0.23 s	3, 4, 6	details
#17	ACCEPTED	0.26 s	3, 4, 6	details
#18	ACCEPTED	0.27 s	3, 4, 6	details
#19	ACCEPTED	0.27 s	3, 4, 6	details
#20	ACCEPTED	0.27 s	3, 4, 6	details
#21	ACCEPTED	0.27 s	3, 4, 6	details
#22	ACCEPTED	0.26 s	3, 4, 6	details
#23	ACCEPTED	0.27 s	3, 4, 6	details
#24	ACCEPTED	0.27 s	3, 4, 6	details
#25	ACCEPTED	0.27 s	3, 4, 6	details
#26	ACCEPTED	0.27 s	3, 4, 6	details
#27	ACCEPTED	0.20 s	3, 4, 6	details
#28	ACCEPTED	0.27 s	4, 6	details
#29	ACCEPTED	0.28 s	4, 6	details
#30	ACCEPTED	0.28 s	4, 6	details
#31	ACCEPTED	0.28 s	4, 6	details
#32	ACCEPTED	0.28 s	4, 6	details
#33	ACCEPTED	0.28 s	4, 6	details
#34	ACCEPTED	0.28 s	4, 6	details
#35	ACCEPTED	0.28 s	4, 6	details
#36	ACCEPTED	0.28 s	4, 6	details
#37	ACCEPTED	0.28 s	4, 6	details
#38	ACCEPTED	0.27 s	4, 6	details
#39	ACCEPTED	0.27 s	4, 6	details
#40	ACCEPTED	0.27 s	4, 6	details
#41	ACCEPTED	0.28 s	4, 6	details
#42	ACCEPTED	0.27 s	4, 6	details
#43	ACCEPTED	0.27 s	4, 6	details
#44	ACCEPTED	0.28 s	4, 6	details
#45	ACCEPTED	0.28 s	4, 6	details
#46	ACCEPTED	0.28 s	4, 6	details
#47	ACCEPTED	0.28 s	4, 6	details
#48	ACCEPTED	0.27 s	4, 6	details
#49	ACCEPTED	0.28 s	4, 6	details
#50	ACCEPTED	0.28 s	4, 6	details
#51	ACCEPTED	0.01 s	5, 6	details
#52	ACCEPTED	0.01 s	5, 6	details
#53	ACCEPTED	0.04 s	5, 6	details
#54	ACCEPTED	0.03 s	5, 6	details
#55	ACCEPTED	0.05 s	5, 6	details
#56	ACCEPTED	0.05 s	5, 6	details
#57	ACCEPTED	0.29 s	6	details
#58	ACCEPTED	0.29 s	6	details
#59	ACCEPTED	0.31 s	6	details
#60	ACCEPTED	0.32 s	6	details
#61	ACCEPTED	0.28 s	6	details
#62	ACCEPTED	0.28 s	6	details

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;

struct edge {
	int u, v, w;
	edge() {}
	edge(int u_, int v_, int w_) : u(u_), v(v_), w(w_) {}
};

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m, k;
	cin >> n >> m >> k;

	vector<set<int>> adj(n);
	vector<int> deg(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--, v--;

		adj[u].insert(v);
		adj[v].insert(u);

		deg[u]++;
		deg[v]++;
	}

	queue<int> que;
	for (int i = 0; i < n; i++) {
		if (deg[i] == 1) {
			que.push(i);
		}
	}

	int s = 0, e = n - 1;

	while (!que.empty()) {
		int u = que.front();
		que.pop();

		if (!deg[u]) {
			assert(false);
		}

		int v = *adj[u].begin();
		adj[v].erase(u);
		if (--deg[v] == 1) {
			que.push(v);
		}

		if (u == s) {
			s = v;
			k--;
		}
		if (u == e) {
			e = v;
			k--;
		}

		if (m == n - 1 && s == e) {
			cout << (k == 0) << "\n";
			return 0;
		}
	}

	if (k < 0) {
		cout << 0 << "\n";
		return 0;
	}
	if (k == 0) {
		cout << (s == e) << "\n";
		return 0;
	}

	vector<bool> special(n, false);
	vector<int> cool;
	int cnt = 0;
	vector<int> mp(n);
	for (int u = 0; u < n; u++) {
		if (deg[u] > 2 || u == s || u == e) {
			mp[u] = cnt++;
			special[u] = true;
			cool.push_back(u);
		}
	}
	assert(cool.size() <= 22);

	set<pair<int, int>> traversed;


	vector<edge> edges;

	auto dfs = [&](auto &oink, int u, int last, int init, int dpth) -> void {
		if (special[u] && !(u == last && u == init)) {
			edges.emplace_back(mp[init], mp[u], dpth);
			edges.emplace_back(mp[u], mp[init], dpth);
			return;
		}
		for (int v : adj[u]) if (!traversed.count({min(u, v), max(u, v)})) {
			traversed.emplace(min(u, v), max(u, v));
			oink(oink, v, u, init, dpth + 1);
		}
	};
	for (int u : cool) {
		dfs(dfs, u, u, u, 0);
	}
	edges.emplace_back(mp[s], mp[s], k + 1);

	vector<vector<ll>> dp(k + 1, vector<ll>(edges.size(), 0));
	dp[0].back() = 1;
	for (int t = 0; t < k; t++) {
		for (int i = 0; i < int(edges.size()); i++) {
			for (int j = 0; j < int(edges.size()); j++) if (j != (i ^ 1) && edges[i].v == edges[j].u && t + edges[j].w <= k) {
				dp[t + edges[j].w][j] = (dp[t + edges[j].w][j] + dp[t][i]) % mod;
			}
		}
	}

	ll res = 0;
	for (int i = 0; i < int(edges.size()); i++) if (edges[i].v == mp[e]) {
		res = (res + dp[k][i]) % mod;
	}
	cout << res << "\n";

	return 0;
}

Test details

Test 1

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

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

correct output
`4` view save

user output
`4` view save

Test 2

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`4 3 4 1 2 2 3 2 4` view save

correct output
`0` view save

user output
`0` view save

Test 3

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`2 1 1 1 2` view save

correct output
`1` view save

user output
`1` view save

Test 4

Subtask: 1, 2, 4, 5, 6

Verdict: ACCEPTED

input
`10 10 5 9 2 9 4 2 5 8 9 ...` view save

correct output
`0` view save

user output
`0` view save

Test 5

Subtask: 1, 2, 4, 5, 6

Verdict: ACCEPTED

input
`10 10 9 8 1 8 7 6 9 3 8 ...` view save

correct output
`1` view save

user output
`1` view save

Test 6

Subtask: 1, 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`10 9 10 1 10 1 7 3 10 9 5 ...` view save

correct output
`0` view save

user output
`0` view save

Test 7

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

input
`10 15 10 5 8 9 10 2 6 7 8 ...` view save

correct output
`414` view save

user output
`414` view save

Test 8

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

input
`10 20 10 7 5 7 8 1 7 10 7 ...` view save

correct output
`15355` view save

user output
`15355` view save

Test 9

Subtask: 1, 2, 5, 6

Verdict: ACCEPTED

input
`10 12 10 8 7 9 8 10 5 5 1 ...` view save

correct output
`8` view save

user output
`8` view save

Test 10

Subtask: 2, 3, 4, 5, 6

Verdict: ACCEPTED

input
`100 99 100 52 8 18 61 38 94 46 100 ...` view save

correct output
`0` view save

user output
`0` view save

Test 11

Subtask: 2, 5, 6

Verdict: ACCEPTED

input
`100 105 100 63 66 58 60 82 95 10 66 ...` view save

correct output
`714878602` view save

user output
`714878602` view save

Test 12

Subtask: 2, 5, 6

Verdict: ACCEPTED

input
`100 110 100 27 10 36 41 21 51 67 70 ...` view save

correct output
`145213422` view save

user output
`145213422` view save

Test 13

Subtask: 2, 5, 6

Verdict: ACCEPTED

input
`100 110 100 96 51 4 38 71 100 19 93 ...` view save

correct output
`524970892` view save

user output
`524970892` view save

Test 14

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 1 134991 60803 22509 116499 162563 3398 95539 36685 ...` view save

correct output
`1` view save

user output
`1` view save

Test 15

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 1 179534 8479 157903 75758 191654 70014 74093 136641 ...` view save

correct output
`0` view save

user output
`0` view save

Test 16

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 2 73737 181461 152353 164598 39854 152630 113800 102119 ...` view save

correct output
`0` view save

user output
`0` view save

Test 17

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 5 1864 74634 151242 167689 134304 34907 31191 144500 ...` view save

correct output
`1` view save

user output
`1` view save

Test 18

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 9582 81551 192132 19534 104640 189666 4048 159986 163627 ...` view save

correct output
`0` view save

user output
`0` view save

Test 19

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 634 120113 131941 86436 121516 73453 144867 154099 187559 ...` view save

correct output
`1` view save

user output
`1` view save

Test 20

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 9999 156360 44775 133399 102816 97578 115279 85426 35248 ...` view save

correct output
`0` view save

user output
`0` view save

Test 21

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 10000 174018 18095 124289 134248 156163 61487 22692 183062 ...` view save

correct output
`0` view save

user output
`0` view save

Test 22

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 9997 42421 142257 68681 66852 23753 189835 15920 152107 ...` view save

correct output
`1` view save

user output
`1` view save

Test 23

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 9997 7257 67775 137368 35287 136873 55062 139502 13649 ...` view save

correct output
`0` view save

user output
`0` view save

Test 24

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 10000 138530 194578 170092 135913 197846 30945 175841 29908 ...` view save

correct output
`0` view save

user output
`0` view save

Test 25

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 10000 50586 65889 97656 199 82172 169565 135247 49398 ...` view save

correct output
`1` view save

user output
`1` view save

Test 26

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 10000 26219 140202 80751 156885 89074 31121 39686 45438 ...` view save

correct output
`0` view save

user output
`0` view save

Test 27

Subtask: 3, 4, 6

Verdict: ACCEPTED

input
`200000 199999 10000 73458 26638 24960 73149 98500 100006 135056 25566 ...` view save

correct output
`0` view save

user output
`0` view save

Test 28

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 4 71063 170999 112262 167446 132778 41726 14927 149461 ...` view save

correct output
`2` view save

user output
`2` view save

Test 29

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9997 93623 73104 143620 21837 140012 178958 169412 155227 ...` view save

correct output
`0` view save

user output
`0` view save

Test 30

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9998 108676 85251 120626 53865 22185 185980 120315 133527 ...` view save

correct output
`1` view save

user output
`1` view save

Test 31

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9999 34043 45894 188478 191792 179114 18866 92725 139966 ...` view save

correct output
`1` view save

user output
`1` view save

Test 32

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 9844 33090 72074 105502 69473 85213 51479 27126 ...` view save

correct output
`0` view save

user output
`0` view save

Test 33

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 8 198227 52374 153592 94277 62798 198081 9747 38403 ...` view save

correct output
`2` view save

user output
`2` view save

Test 34

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9999 38948 87012 75557 104481 136914 651 63353 76448 ...` view save

correct output
`0` view save

user output
`0` view save

Test 35

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 114749 43409 197006 178268 178476 26621 148333 1852 ...` view save

correct output
`2` view save

user output
`2` view save

Test 36

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9849 128248 41928 102409 136212 21468 167482 162722 46907 ...` view save

correct output
`1` view save

user output
`1` view save

Test 37

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9850 180582 124939 11693 87470 171894 114673 151571 38440 ...` view save

correct output
`0` view save

user output
`0` view save

Test 38

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9850 184412 83268 128807 44170 26253 126339 120550 69131 ...` view save

correct output
`2` view save

user output
`2` view save

Test 39

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 116047 12970 63831 182104 111914 38753 145557 89749 ...` view save

correct output
`2` view save

user output
`2` view save

Test 40

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 161162 192005 173486 5799 121169 117517 131073 50233 ...` view save

correct output
`1` view save

user output
`1` view save

Test 41

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9999 161162 192005 173486 5799 121169 117517 131073 50233 ...` view save

correct output
`0` view save

user output
`0` view save

Test 42

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9999 121115 10494 196280 116808 144717 31998 130883 84826 ...` view save

correct output
`1` view save

user output
`1` view save

Test 43

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9998 121115 10494 196280 116808 144717 31998 130883 84826 ...` view save

correct output
`0` view save

user output
`0` view save

Test 44

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 157121 120558 112994 175263 171516 106269 163986 185595 ...` view save

correct output
`2` view save

user output
`2` view save

Test 45

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 9999 15645 65909 109001 114704 48122 116792 138487 55081 ...` view save

correct output
`0` view save

user output
`0` view save

Test 46

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 78578 123492 77698 40519 84219 64149 93230 51551 ...` view save

correct output
`2` view save

user output
`2` view save

Test 47

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 125797 61162 25525 189681 178938 104343 127938 99958 ...` view save

correct output
`0` view save

user output
`0` view save

Test 48

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 1 63340 1 117445 113745 1 194456 1 ...` view save

correct output
`2` view save

user output
`2` view save

Test 49

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 146958 200000 200000 54040 68156 200000 200000 55718 ...` view save

correct output
`2` view save

user output
`2` view save

Test 50

Subtask: 4, 6

Verdict: ACCEPTED

input
`200000 200000 10000 75759 1 1 122977 1 108735 1 44452 ...` view save

correct output
`0` view save

user output
`0` view save

Test 51

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1001 10000 270 328 167 836 209 262 544 73 ...` view save

correct output
`97138096` view save

user output
`97138096` view save

Test 52

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1005 10000 136 141 633 688 219 129 341 622 ...` view save

correct output
`841074570` view save

user output
`841074570` view save

Test 53

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1010 10000 173 575 691 507 521 654 269 631 ...` view save

correct output
`724704425` view save

user output
`724704425` view save

Test 54

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1010 10000 904 1000 236 1000 1000 316 1000 948 ...` view save

correct output
`864991067` view save

user output
`864991067` view save

Test 55

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1010 10000 431 889 501 636 7 582 462 868 ...` view save

correct output
`970435703` view save

user output
`970435703` view save

Test 56

Subtask: 5, 6

Verdict: ACCEPTED

input
`1000 1010 10000 246 207 963 273 738 223 695 924 ...` view save

correct output
`27240937` view save

user output
`27240937` view save

Test 57

Subtask: 6

Verdict: ACCEPTED

input
`200000 200001 10000 73346 12940 91788 126866 191845 196823 1771 45039 ...` view save

correct output
`980044634` view save

user output
`980044634` view save

Test 58

Subtask: 6

Verdict: ACCEPTED

input
`200000 200005 10000 97853 177374 174818 82833 175749 181739 160817 150566 ...` view save

correct output
`883528742` view save

user output
`883528742` view save

Test 59

Subtask: 6

Verdict: ACCEPTED

input
`200000 200010 10000 8593 121197 90934 103451 173940 157010 55274 145619 ...` view save

correct output
`79062217` view save

user output
`79062217` view save

Test 60

Subtask: 6

Verdict: ACCEPTED

input
`200000 200010 10000 138445 200000 41553 200000 141229 200000 53521 200000 ...` view save

correct output
`864991067` view save

user output
`864991067` view save

Test 61

Subtask: 6

Verdict: ACCEPTED

input
`200000 200010 10000 9917 200000 24783 200000 200000 39037 14350 37168 ...` view save

correct output
`471882140` view save

user output
`471882140` view save

Test 62

Subtask: 6

Verdict: ACCEPTED

input
`200000 200010 10000 80269 156844 9747 1 104448 1 1 134193 ...` view save

correct output
`235428850` view save

user output
`235428850` view save

BOI 2026 Mirror Day 1

Tourist's Journey

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

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Test 54

Test 55

Test 56

Test 57

Test 58

Test 59

Test 60

Test 61

Test 62

Tasks

Submissions (frederikvase)