oj.uz

Submission #973997

# Submission time Handle Problem Language Result Execution time Memory
973997 2024-05-02T14:34:47 Z NotLinux Village (BOI20_village) C++17
12 / 100
 700 ms 4948 KB 
//author : FatihCihan
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
const int N = 1e5 + 7;
const int M = 20;
const int inf = 1e9 + 7;
int n , lift[N][M] , depth[N];
vector < int > tree[N];
void dfs(int node , int par){
	depth[node] = depth[par] + 1;
	lift[node][0] = par;
	for(auto itr : tree[node]){
		if(itr != par){
			dfs(itr , node);
		}
	}
}
int find_lca(int a , int b){
	if(depth[a] < depth[b])swap(a , b);
	int diff = depth[a] - depth[b];
	for(int i = 0;i<M;i++){
		if(diff & (1 << i)){
			a = lift[a][i];
		}
	}
	if(a == b)return a;
	for(int i = M-1;i>=0;i--){
		if(lift[a][i] != lift[b][i]){
			a = lift[a][i] , b = lift[b][i];
		}
	}
	return lift[a][0];
}
int find_dist(int a , int b){
	int lc = find_lca(a , b);
	return depth[a] + depth[b] - 2 * depth[lc];
}
void solve(){
	cin >> n;
	for(int i = 1;i<n;i++){
		int a,b;
		cin >> a >> b;
		tree[a].push_back(b);
		tree[b].push_back(a);
	}
	dfs(1 , 0);
	for(int i = 1;i<M;i++){
		for(int j = 1;j<=n;j++){
			lift[j][i] = lift[lift[j][i-1]][i-1];
		}
	}
	vector < int > perm(n) , v_mn , v_mx;
	iota(all(perm) , 1);
	int mn_ans = inf , mx_ans = -inf;
	do{
		bool flag = 0;
		for(int i = 0;i<n;i++){
			if(perm[i] == (i+1))flag = 1;
		}
		if(flag)continue;
		int cost = 0;
		for(int i = 0;i<n;i++){
			cost += find_dist(i+1 , perm[i]);
		}
		if(cost < mn_ans){
			mn_ans = cost;
			v_mn = perm;
		}
		if(cost > mx_ans){
			mx_ans = cost;
			v_mx = perm;
		}
	} while(next_permutation(all(perm)));
	cout << mn_ans << " " << mx_ans << endl;
	for(auto itr : v_mn)cout << itr << " ";cout << endl;
	for(auto itr : v_mx)cout << itr << " ";cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase = 1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

Compilation message

Village.cpp: In function 'void solve()':
Village.cpp:77:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   77 |  for(auto itr : v_mn)cout << itr << " ";cout << endl;
      |  ^~~
Village.cpp:77:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   77 |  for(auto itr : v_mn)cout << itr << " ";cout << endl;
      |                                         ^~~~
Village.cpp:78:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   78 |  for(auto itr : v_mx)cout << itr << " ";cout << endl;
      |  ^~~
Village.cpp:78:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   78 |  for(auto itr : v_mx)cout << itr << " ";cout << endl;
      |                                         ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 5 ms 4740 KB Output is correct
9 Correct 44 ms 4716 KB Output is correct
10 Correct 486 ms 4712 KB Output is correct
11 Correct 360 ms 4724 KB Output is correct
12 Correct 416 ms 4948 KB Output is correct
13 Correct 499 ms 4948 KB Output is correct
14 Correct 485 ms 4696 KB Output is correct
15 Correct 526 ms 4720 KB Output is correct
16 Correct 535 ms 4720 KB Output is correct
17 Correct 508 ms 4724 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1022 ms 4700 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4696 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 2 ms 4696 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct
6 Correct 2 ms 4700 KB Output is correct
7 Correct 2 ms 4700 KB Output is correct
8 Correct 5 ms 4740 KB Output is correct
9 Correct 44 ms 4716 KB Output is correct
10 Correct 486 ms 4712 KB Output is correct
11 Correct 360 ms 4724 KB Output is correct
12 Correct 416 ms 4948 KB Output is correct
13 Correct 499 ms 4948 KB Output is correct
14 Correct 485 ms 4696 KB Output is correct
15 Correct 526 ms 4720 KB Output is correct
16 Correct 535 ms 4720 KB Output is correct
17 Correct 508 ms 4724 KB Output is correct
18 Execution timed out 1022 ms 4700 KB Time limit exceeded
19 Halted 0 ms 0 KB -