CSES - Datatähti Open 2021 - Results
Submission details
Task:Distances
Sender:wabadaba
Submission time:2021-01-31 19:47:49 +0200
Language:C++17
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
Test results
testverdicttimegroup
#10.01 s1, 2details
#20.01 s2details

Compiler report

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from input/code.cpp:1:
input/code.cpp: In function 'void solve()':
input/code.cpp:170:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  assert(ans.size() <= n+1);
         ~~~~~~~~~~~^~~~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

// change ld to db if neccesary
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pld;

typedef set<int> si;
typedef set<ll> sl;
typedef set<ld> sld;
typedef set<str> ss;
typedef set<pi> spi;
typedef set<pl> spl;
typedef set<pld> spld;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vld;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<si> vsi;
typedef vector<sl> vsl;
typedef vector<pld> vpld;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound

#define forr(i,a,b) for (int i = (a); i < (b); i++)
#define ford(i,a,b) for (int i = (a)-1; i >= (b); i--)
#define trav(a,x) for (auto& a: x)

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
int pct(int x) { return __builtin_popcount(x); }
int bits(int x) { return 31-__builtin_clz(x); } // floor(log2(x))
int fstTrue(function<bool(int)> f, int lo, int hi) {
	hi ++; assert(lo <= hi); // assuming f is increasing
	while (lo < hi) { // find first index such that f is true
		int mid = (lo+hi)/2;
		f(mid) ? hi = mid : lo = mid+1;
	}
	return lo;
}

const ll MOD = 1e9+7;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
int gcd(int a,int b){return b?gcd(b,a%b):a;}
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
bool sortcol(const vl& v1, const vl& v2) {return v1[1] < v2[1];}
bool sortpair(const pi& p1, const pi& p2) {return p1.f < p2.f;}

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<long long unsigned> distribution(0,10);

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
// void __print(mi x) {cerr << x;}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define dbg(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define dbg(x...)
#endif

const int mxN = 2e5+5;
int n, par[105];
si adj[105];
bool vis[105];
vi ans;

// void setvis(int x) {
// 	if (!vis[x]) {
// 		vis[x] = 1;
// 		num++;
// 		ans.pb(x);
// 	}
// }
void dfs(int x = 0, int p = -1) {
	par[x] = p;
	if (x) adj[x].erase(p);
	trav(i,adj[x]) if (i != p) dfs(i,x);
}
void solve() {
	cin >> n;
	forr(i,0,n-1) {
		int a, b; cin >> a >> b; a--, b--;
		adj[a].ins(b);
		adj[b].ins(a);
	}
	dfs();
	int num = 1, pos = 0;
	ans.pb(0);
	vis[0] = 1;
	while (num < n) {
		// vis[pos] = 1;
		// num++;
		// ans.pb(pos);
		if (!adj[pos].size()) {
			forr(i,0,3) {
				pos = par[pos];
				if (pos == -1) break;
				if (adj[pos].size() >= 2) {
					adj[pos].erase(adj[pos].begin());
					forr(j,i+1,3) if (adj[pos].size()) pos = *adj[pos].begin();
					// setvis(pos);
					// assert(!vis[pos]);
					vis[pos] = 1;
					num++;
					ans.pb(pos);
					break;
				} 
				// else setvis(pos);
				else if (!vis[pos]) {
					vis[pos] = 1;
					num++;
					ans.pb(pos);
				}
			}
		}
		else {
			forr(i,0,3) if (adj[pos].size()) pos = *adj[pos].begin();
			// setvis(pos);
			// dbg(pos);
			// assert(!vis[pos]);
			vis[pos] = 1;
			num++;
			ans.pb(pos);
		}
	}
	assert(ans.size() <= n+1);
	trav(i,ans) cout << i+1 << " ";
	cout << "\n";
	fill(par,par+105,0), fill(vis,vis+105,0);
	forr(i,0,105) adj[i].clear();
	ans.clear();
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	// freopen(".in", "r", stdin);
	// freopen(".out", "w", stdout);

	int tc = 1;
	cin >> tc;
	while (tc--) solve();
}

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
1 3 5 6 2 7 8 4 
1 8 2 7 3 2 2 2 
1 8 7 2 5 6 3 5 
1 5 2 4 7 3 8 6 
1 6 4 2 5 7 3 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
1 60 12 11 47 93 19 47 47 47 4...