Submission #1020248

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1020248	2024-07-11T18:16:35 Z	ali2241	Village (BOI20_village)	C++17	12 / 100	74 ms	3664 KB

Village

#include <bits/stdc++.h>
//ali2241

using namespace std;
#define int long long
//using ll = __int128;
using ld = long double;
const int M = 10589;
const int N = 1001;

vector<int> adj[N];
int dis[N][N];
int get (int a, int b, int c = -1) {
	if (a == b) {
		return 0;
	}
	int ans = -1e9;

    for (int i : adj[a]) {
		if (i != c)
		ans = max(ans, get(i, b, a));
	}
	return ans + 1;
}
int fact(int n) {
	if (n == 0)
	return 1;
	return n * fact(n - 1);
}
void fun() {
    int n;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
    	int a, b;
    	cin >> a >> b;
    	adj[a].push_back(b);
    	adj[b].push_back(a);
	}
	pair<int, vector<int>> mn = {1e9, {}};
	pair<int, vector<int>> mx = {-1e9, {}};
	vector<int> per;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) {
			dis[i][j] = get(i, j);
		}
	}
	for (int i = 1; i <= n; ++i) {
		per.push_back(i);
	}
	for (int i = 0; i < fact(n); ++i) {
		int ths = 0;
		bool b = 0;
		for (int i = 0; i < n; ++i) {
			if (i + 1 == per[i]) {
				b = 1;
				continue;
			}
			ths += dis[i + 1][per[i]];
		}
		if (ths < mn.first and !b) {
			mn = {ths, per};
		}
		if (ths > mx.first and !b) {
			mx = {ths, per};
		}
		next_permutation(per.begin(), per.end());
	}
	cout << mn.first << " " << mx.first << "\n";
	for (int i = 0; i < n; ++i) {
		cout << mn.second[i] << " ";
	}
	cout << "\n";
	for (int i = 0; i < n; ++i) {
		cout << mx.second[i] << " ";
	}
}

int32_t main() {
//    freopen("output.txt", "w", stdout);
//    freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(0);
    int tc = 1;
    while (tc--)
        fun();
}

Subtask #1

12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	488 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	6 ms	484 KB	Output is correct
10	Correct	74 ms	504 KB	Output is correct
11	Correct	54 ms	348 KB	Output is correct
12	Correct	56 ms	344 KB	Output is correct
13	Correct	57 ms	600 KB	Output is correct
14	Correct	71 ms	344 KB	Output is correct
15	Correct	67 ms	344 KB	Output is correct
16	Correct	62 ms	348 KB	Output is correct
17	Correct	55 ms	344 KB	Output is correct

Subtask #2

0.0 / 38.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	57 ms	3664 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 50.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	488 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	6 ms	484 KB	Output is correct
10	Correct	74 ms	504 KB	Output is correct
11	Correct	54 ms	348 KB	Output is correct
12	Correct	56 ms	344 KB	Output is correct
13	Correct	57 ms	600 KB	Output is correct
14	Correct	71 ms	344 KB	Output is correct
15	Correct	67 ms	344 KB	Output is correct
16	Correct	62 ms	348 KB	Output is correct
17	Correct	55 ms	344 KB	Output is correct
18	Runtime error	57 ms	3664 KB	Execution killed with signal 11
19	Halted	0 ms	0 KB	-