CSES - Aalto Competitive Programming 2024 - wk12 - Mon

CSES - Aalto Competitive Programming 2024 - wk12 - Mon - Results

Submission details
Task:	Creating Offices
Sender:	aalto2024m_002
Submission time:	2024-11-25 16:44:33 +0200
Language:	C++ (C++20)
Status:	READY
Result:	WRONG ANSWER

Test results
test	verdict	time
#1	ACCEPTED	0.00 s	details
#2	ACCEPTED	0.00 s	details
#3	ACCEPTED	0.00 s	details
#4	WRONG ANSWER	0.00 s	details
#5	ACCEPTED	0.00 s	details
#6	ACCEPTED	0.16 s	details
#7	ACCEPTED	0.11 s	details
#8	WRONG ANSWER	0.15 s	details
#9	WRONG ANSWER	0.16 s	details
#10	WRONG ANSWER	0.15 s	details
#11	ACCEPTED	0.17 s	details
#12	ACCEPTED	0.09 s	details
#13	ACCEPTED	0.14 s	details
#14	WRONG ANSWER	0.15 s	details
#15	WRONG ANSWER	0.15 s	details
#16	ACCEPTED	0.08 s	details
#17	WRONG ANSWER	0.11 s	details
#18	ACCEPTED	0.00 s	details
#19	ACCEPTED	0.09 s	details
#20	WRONG ANSWER	0.10 s	details
#21	WRONG ANSWER	0.00 s	details
#22	WRONG ANSWER	0.10 s	details

Code

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// Debug printing
#ifdef DEBUG
#define deb(fmt, args...) printf("DEBUG: %d: " fmt, __LINE__, ##args)
#define debug_print(fmt, args...) printf(fmt, ##args)
#else
#define deb(fmt, args...)
#define debug_print(fmt, args...)
#endif

void print_array(vector<int> in, const string title = "Vector")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		debug_print("%d ", in[i]);
	}
	debug_print("\nDEBUG: ] END\n");
}

void print_matrix(vector<vector<int>> in, const string title = "Matrix")
{
	debug_print("DEBUG: %s [\nDEBUG: ", title.c_str());
	for (unsigned int i = 0; i < in.size(); i++) {
		for (unsigned int j = 0; j < in[i].size(); j++) {
			debug_print("%d ", in[i][j]);
		}
		debug_print("\nDEBUG: ");
	}
	debug_print("DEBUG: ] END\n");
}

int dfs(int s, vector<bool> &visited, vector<vector<int>> &adj, int d, int dprev, vector<int> &res)
{
	if (visited[s]) {
		return dprev + 1;
	};
	visited[s] = true;
	int dthis = dprev;
	if (dprev == d) {
		res.push_back(s);
		dthis = 0;
	}
	// deb("start: %d\n", s);

	// Do something with this node

	for (auto u : adj[s]) {
		// deb("dthis: %d, nbour: %d\n", dthis, u);
		int a = dfs(u, visited, adj, d, dthis + 1, res);
		dthis = min(a, dthis);
	}
	return dthis + 1;
}

int main(int argc, char *argv[])
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	// Read the input parameters
	int n, d;
	cin >> n >> d;

	// Read pairs from multiple lines
	vector<vector<int>> adj(n + 1, vector<int>());
	int a, b;
	for (int i = 1; i < n; i++) {
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}

	int start = 0;
	for (int i = 1; i < n + 1; i++) {
		if (adj[i].size() == 1) {
			start = i;
			break;
		}
	}

	// print_matrix(adj);
	// deb("start: %d\n", start);

	vector<bool> visited(n + 1, false);
	vector<int> res;
	res.push_back(start);
	dfs(start, visited, adj, d, 0, res);

	cout << res.size() << "\n";
	for (unsigned int i = 0; i < res.size(); i++) {
		cout << res[i] << " ";
	}
	cout << "\n";
	
	return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
`10 3 5 10 8 7 1 4 3 5 ...` view save

correct output
`4 1 3 8 9` view save

user output
`4 8 1 3 9` view save

Test 2

Verdict: ACCEPTED

input
`10 5 8 7 8 2 8 5 8 3 ...` view save

correct output
`1 10` view save

user output
`1 1` view save

Test 3

Verdict: ACCEPTED

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

correct output
`2 1 4` view save

user output
`2 1 4` view save

Test 4

Verdict: WRONG ANSWER

input
`10 4 8 5 8 6 1 8 4 9 ...` view save

correct output
`3 3 9 10` view save

user output
`2 2 5` view save

Test 5

Verdict: ACCEPTED

input
`10 3 7 8 1 10 4 3 1 5 ...` view save

correct output
`4 3 8 9 10` view save

user output
`4 3 10 8 9` view save

Test 6

Verdict: ACCEPTED

input
`200000 9 7112 139320 131799 678 101561 62983 190924 56029 ...` view save

correct output
`22223 7 27 28 29 34 35 53 63 65 71 7...` view save

user output
`22223 104543 173442 43755 139047 900...` Truncated

Test 7

Verdict: ACCEPTED

input
`200000 1 117863 108209 117863 142206 117863 98558 117863 124329 ...` view save

correct output
`200000 1 2 3 4 5 6 7 8 9 10 11 12 13 ...` view save

user output
`200000 1 117863 108209 142206 98558 1...` Truncated

Test 8

Verdict: WRONG ANSWER

input
`200000 2 196127 1313 59937 27170 188592 185528 106118 64586 ...` view save

correct output
`119174 1 2 7 8 9 10 11 14 16 17 18 19...` view save

user output
`100123 1 125432 106982 78631 188095 1...` Truncated

Test 9

Verdict: WRONG ANSWER

input
`200000 3 174335 181372 73884 35338 65409 30522 120927 7911 ...` view save

correct output
`66675 10 30 31 39 42 46 48 52 54 55 ...` view save

user output
`66654 469 125343 170618 125294 17683...` Truncated

Test 10

Verdict: WRONG ANSWER

input
`200000 9 156193 90960 92081 42156 64080 41287 65601 109953 ...` view save

correct output
`22257 8 14 30 42 59 62 74 82 99 103 ...` view save

user output
`22030 490 92332 101647 84275 68046 1...` Truncated

Test 11

Verdict: ACCEPTED

input
`200000 200000 183551 137559 138103 16820 21892 134252 182028 187950 ...` view save

correct output
`1 40760` view save

user output
`1 40760` view save

Test 12

Verdict: ACCEPTED

input
`200000 459 30507 105253 30507 95541 30507 161230 30507 135274 ...` view save

correct output
`1 200000` view save

user output
`1 1` view save

Test 13

Verdict: ACCEPTED

input
`200000 327 43832 190820 78666 45374 184224 57261 193962 158173 ...` view save

correct output
`1 181355` view save

user output
`1 5` view save

Test 14

Verdict: WRONG ANSWER

input
`200000 217 31004 146202 108924 82624 43788 48134 199877 157947 ...` view save

correct output
`924 279 304 418 471 539 566 713 10...` view save

user output
`899 304 29364 51445 85852 40922 14...` Truncated

Test 15

Verdict: WRONG ANSWER

input
`200000 475 77454 87171 23492 138432 137402 34171 181862 18661 ...` view save

correct output
`394 833 915 982 2281 2467 2531 267...` view save

user output
`271 658 143774 38258 138491 197048...` Truncated

Test 16

Verdict: ACCEPTED

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

correct output
`99999 3 5 7 9 11 13 15 17 19 21 23 2...` view save

user output
`99999 3 5 7 9 11 13 15 17 19 21 23 2...` Truncated

Test 17

Verdict: WRONG ANSWER

input
`199397 946 29518 79973 29518 71183 71183 194147 29518 156561 ...` view save

correct output
`159 52 101 164 243 252 621 1256 37...` view save

user output
`52 52 106223 122046 175080 139281...` Truncated

Test 18

Verdict: ACCEPTED

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

correct output
`2 1 5` view save

user output
`2 1 4` view save

Test 19

Verdict: ACCEPTED

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

correct output
`40 4397 9397 14397 19397 24397 29...` view save

user output
`40 1 5001 10001 15001 20001 25001...` Truncated

Test 20

Verdict: WRONG ANSWER

input
`199397 945 29518 79973 29518 71183 71183 194147 29518 156561 ...` view save

correct output
`160 52 101 164 243 252 621 1256 37...` view save

user output
`52 52 57445 122046 175080 139281 ...` Truncated

Test 21

Verdict: WRONG ANSWER

input
`1 1` view save

correct output
`1 1` view save

user output
`1 0` view save

Test 22

Verdict: WRONG ANSWER

input
`199397 899 29518 79973 29518 71183 71183 194147 29518 156561 ...` view save

correct output
`183 52 101 164 243 252 621 792 125...` view save

user output
`52 52 88029 122046 175080 139281 ...` Truncated

Aalto Competitive Programming 2024 - wk12 - Mon

Creating Offices

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

Tasks

Submissions (aalto2024m_002)