CSES - Datatähti 2021 loppu - Results
Submission details
Task:Etäisyydet
Sender:hltk
Submission time:2021-01-23 17:28:34 +0200
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED29
#2ACCEPTED71
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s2details

Code

#include <functional>
#include <iostream>
#include <vector>
using namespace std;

void solve() {
	int n;
	cin >> n;

	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	vector<int> dep(n);
	function<void(int, int)> dfs1 = [&](int s, int e) {
		for (auto& u : g[s]) {
			if (u == e) continue;
			dep[u] = dep[s] + 1;
			dfs1(u, s);
		}
	};
	dfs1(0, 0);

	vector<int> vis(n);
	function<void(int)> dfs2 = [&](int s) {
		cout << s + 1 << " ";
		vis[s] = 1;
		function<pair<int, int>(int, int, int)> dfs3 = [&](int s, int e, int d) -> pair<int, int> {
			pair<int, int> ret{dep[s], s};
			if (vis[s]) ret.first = -1;
			if (d == 0) return ret;
			for (auto& u : g[s]) {
				if (u == e) continue;
				ret = max(ret, dfs3(u, s, d - 1));
			}
			return ret;
		};
		auto [d, u] = dfs3(s, s, 3);
		if (d == -1) return;
		dfs2(u);
	};
	dfs2(0);
	cout << "\n";
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int t;
	cin >> t;
	for (int i = 0; i < t; ++i) solve();
}

Test details

Test 1

Group: 1, 2

Verdict: ACCEPTED

input
100
8
5 2
2 3
3 7
...

correct output
1 8 2 5 6 7 3 4 
1 7 2 8 3 6 4 5 
1 4 6 2 7 5 8 3 
1 8 3 2 4 7 6 5 
1 6 4 7 5 2 3 8 
...

user output
1 3 6 5 7 2 8 4 
1 8 2 7 5 6 4 3 
1 8 7 5 2 6 4 3 
1 3 8 7 4 2 6 5 
1 3 5 2 7 4 8 6 
...

Test 2

Group: 2

Verdict: ACCEPTED

input
100
100
37 59
81 37
44 81
...

correct output
1 99 82 81 59 5 71 55 17 24 13...

user output
1 60 93 47 11 12 44 98 72 31 7...