oj.uz

Submission #1087552

# Submission time Handle Problem Language Result Execution time Memory
1087552 2024-09-12T22:28:32 Z freedommo33 Village (BOI20_village) C++17
12 / 100
 48 ms 604 KB 
#include <bits/stdc++.h>
typedef long long ll;
constexpr int M = 25;
using namespace std;
vector<vector<int>> g(M);
int odl[M][M]; 
int makstab[M];
int mintab[M];
void bfs(int v){
	queue<int> q;
	q.push(v);
	while(!q.empty()){
		int p = q.front();
		q.pop();
		for(auto i:g[p]) if(odl[v][i] == 0 && i != v){
			odl[v][i] = odl[v][p] + 1;
			q.push(i);
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	int mini = 21376969;
	int maks = 0;
	for(int i=1; i<n; i++){
		int a, b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1; i<=n; i++) bfs(i);
	vector<int> v;
	for(int i=1; i<=n; i++) v.push_back(i);
	do{
		bool czy = 0;
		for(int i=1; i<=n; i++) if(v[i-1] == i) czy = 1;
		if(czy==1) continue;
		int akt = 0;
		for(int i=1; i<=n; i++) akt += odl[v[i-1]][i];
		if(mini > akt){
			mini = akt;
			for(int i=1; i<=n; i++) mintab[i] = v[i-1];
		}
		if(maks < akt){
			maks = akt;
			for(int i=1; i<=n; i++) makstab[i] = v[i-1];
		}
	}while(next_permutation(v.begin(), v.end()));
	cout<<mini<<" "<<maks<<endl;
	for(int i=1; i<=n; i++) cout<<mintab[i]<<" ";
	cout<<endl;
	for(int i=1; i<=n; i++) cout<<makstab[i]<<" ";
	cout<<endl;
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 43 ms 348 KB Output is correct
11 Correct 45 ms 440 KB Output is correct
12 Correct 46 ms 348 KB Output is correct
13 Correct 48 ms 348 KB Output is correct
14 Correct 44 ms 456 KB Output is correct
15 Correct 45 ms 348 KB Output is correct
16 Correct 43 ms 348 KB Output is correct
17 Correct 44 ms 348 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 604 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 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 5 ms 348 KB Output is correct
10 Correct 43 ms 348 KB Output is correct
11 Correct 45 ms 440 KB Output is correct
12 Correct 46 ms 348 KB Output is correct
13 Correct 48 ms 348 KB Output is correct
14 Correct 44 ms 456 KB Output is correct
15 Correct 45 ms 348 KB Output is correct
16 Correct 43 ms 348 KB Output is correct
17 Correct 44 ms 348 KB Output is correct
18 Runtime error 0 ms 604 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -