CSES - Datatähti Open 2021 - Results
Submission details
Task:Distances
Sender:lakshith-403
Submission time:2021-01-30 14:21:39 +0200
Language:C++11
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1, 2details
#20.01 s2details

Code

#include <bits/stdc++.h>

#define ll long long
#define what_is(a) cout << #a << " is " << a << "\n";
#define check(a) cout << "reached " << a << "\n";

using namespace std;

vector<int> ans;

void dfs(int n,int d,vector<vector<int>> &adjList,int* v){
	bool flag = false;
	//check(n+1)
	//what_is(d)
	if(d==2){
		v[n]=1;
		ans.push_back(n);
	}

	
	for(int x:adjList[n]){
		if(v[x])continue;
		if(d==1){
			flag = true;
			dfs(x,2,adjList,v);
		}else{
			dfs(x,1,adjList,v);
		}
	}

	for(int x:adjList[n]){
		if(v[x]&&d==1)continue;
		if(d==1){
			flag = true;
			dfs(x,2,adjList,v);
		}else{
			dfs(x,1,adjList,v);
		}
	}
	if(!flag && d==1 && v[n]==0)
	dfs(n,2,adjList,v);
}

void solve(int T){
	ans = vector<int>();
	int n;
	cin >> n;
	vector<vector<int>> adjList(n,vector<int>());
	for(int i=0;i<n-1;i++){
		int x,y;
		cin >> x >> y;
		x--,y--;
		adjList.at(x).push_back(y);
		adjList.at(y).push_back(x);
	}
	int leaf =0;
	for(int i=0;i<n;i++)if(adjList.at(i).size()==1)leaf = i;
	int v[n];
	memset(v,0,sizeof(v));
	//what_is(leaf)
	dfs(leaf,2,adjList,v);
	for(int u:ans)cout << u+1 << " ";
	cout << "\n";
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int t;
	cin >> t;
	while(t--)
	solve(t);
}

/*
 1
 7
 1 2
 2 3
 3 4
 2 5
 5 6
 5 7
  */

Test details

Test 1

Group: 1, 2

Verdict:

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
7 2 5 3 4 8 1 6 
6 1 7 2 8 3 5 4 
7 8 3 4 1 6 2 5 
7 8 2 4 1 6 3 5 
6 8 1 4 7 3 2 5 
...

Test 2

Group: 2

Verdict:

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

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

user output
92 94 97 54 61 6 70 56 63 72 2...