oj.uz

답안 #1020248

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1020248 2024-07-11T18:16:35 Z ali2241 Village (BOI20_village) C++17
12 / 100
 74 ms 3664 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -