Etäisyydet

#include <bits/stdc++.h>

typedef long long ll;

#define M 1000000007
#define N (1 << 18)

using namespace std;

int dst[101][101];
int n;
bool f = 0;
vector<int> v[101];

void find(int s, int cur, int e, int d) {
    dst[s][cur] = d;
    //cout << s << ", " << cur << " e: " << e << endl;
    for (int u : v[cur]) {
        if (u == e) continue;
        find(s, u, cur, d + 1);
    }
}

int order[101];
int vis[101];

void brute(int cur) {
    if (f) return;
    if (cur == n) {
        for (int i = 0; i < n; ++i) {
            cout << order[i] << " ";
        }
        f = 1;
        return;
    } else {
        for (int i = 1; i <= n; ++i) {
            if (vis[i]) continue;
            if (dst[order[cur - 1]][i] > 3) continue;
            vis[i] = 1;
            order[cur] = i;
            brute(cur + 1);
            vis[i] = 0;
        }
    }
}

vector<pair<int, int>> nv[101];

void b2(int cur) {
    if (f) return;
    if (cur == n) {
        for (int i = 0; i < n; ++i) {
            cout << order[i] << " ";
        }
        f = 1;
        return;
    } else {
        for (auto p : nv[order[cur - 1]]) {
            int u = p.second;
            if (vis[u]) continue;
            vis[u] = 1;
            order[cur] = u;
            b2(cur + 1);
            vis[u] = 0;
        }
        /*for (int i = 1; i <= n; ++i) {
            if (vis[i]) continue;
            if (dst[order[cur - 1]][i] > 3) continue;
            vis[i] = 1;
            order[cur] = i;
            brute(cur + 1);
            vis[i] = 0;
        }*/
    }
}

void test_case() {
    f = 0;
	cin >> n;
    for (int i = 0; i <= n; ++i) {
        v[i].clear();
    }
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    //cout << "hre" << endl;
    for (int i = 1; i <= n; ++i) {
        find(i, i, -1, 0);
    }

    for (int i = 0; i <= n; ++i) {
        v[i].clear();
        nv[i].clear();
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (i == j) continue;
            if (dst[i][j] <= 3) {
                v[i].push_back(j);
                v[j].push_back(i);
            }
        }
    }
    vector<pair<int, int>> so;
    for (int i = 1; i <= n; ++i) {
        so.push_back({v[i].size(), i});
        for (int u : v[i]) {
            nv[i].push_back({v[u].size(), u});
        }

        sort(nv[i].rbegin(), nv[i].rend());
    }

    sort(so.begin(), so.end());
    //cout << "hre" << endl;

    /*for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << "i: " << i << " j: " << j << " d:" << dst[i][j] << endl;
        }
    }*/

    for (auto p : so) {
        int i = p.second;
        vis[i] = 1;
        order[0] = i;
        b2(1);
        vis[i] = 0;
    }

}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int t = 0;
	cin >> t;
	for (int i = 0; i < t; ++i) {
		test_case();
		cout << "\n";
	}

	return 0;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: TIME LIMIT EXCEEDED