oj.uz

Submission #977298

# Submission time Handle Problem Language Result Execution time Memory
977298 2024-05-07T17:07:14 Z aeg Village (BOI20_village) C++14
12 / 100
 418 ms 600 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MAX=10+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;

int n;
vector<int> G[MAX];

int dfs(int v,int p,int d,int tar) {
	if (v==tar) return d;
	for (int i:G[v]) {
		if (i==p) continue;
		int rlt=dfs(i,v,d+1,tar);
		if (rlt!=-1) return rlt;
	}
	return -1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int perm[11]={0,1,2,3,4,5,6,7,8,9,10};
	int ans[11];
	int ans2[11];
	int maxx=0;
	int minn=INF;
	do {
		for (int i=1;i<=n;i++) {
			if (perm[i]==i) goto die;
		}
		{
			int ttl=0;
			for (int i=1;i<=n;i++) {
				ttl+=dfs(i,0,0,perm[i]);
			}
			if (ttl>maxx) {
				maxx=ttl;
				for (int i=1;i<=n;i++) {
					ans[i]=perm[i];
				}
			}
			if (ttl<minn) {
				minn=ttl;
				for (int i=1;i<=n;i++) {
					ans2[i]=perm[i];
				}
			}
		}
		die:
		;
	} while (next_permutation(perm+1,perm+n+1));
	cout<<minn<<" "<<maxx<<"\n";
	for (int i=1;i<=n;i++) {
		cout<<ans2[i]<<" ";
	}
	cout<<"\n";
	for (int i=1;i<=n;i++) {
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 30 ms 348 KB Output is correct
10 Correct 328 ms 344 KB Output is correct
11 Correct 388 ms 348 KB Output is correct
12 Correct 324 ms 444 KB Output is correct
13 Correct 356 ms 428 KB Output is correct
14 Correct 418 ms 432 KB Output is correct
15 Correct 363 ms 432 KB Output is correct
16 Correct 364 ms 344 KB Output is correct
17 Correct 335 ms 428 KB Output is correct

Subtask #2
0.0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 348 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 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 600 KB Output is correct
8 Correct 4 ms 344 KB Output is correct
9 Correct 30 ms 348 KB Output is correct
10 Correct 328 ms 344 KB Output is correct
11 Correct 388 ms 348 KB Output is correct
12 Correct 324 ms 444 KB Output is correct
13 Correct 356 ms 428 KB Output is correct
14 Correct 418 ms 432 KB Output is correct
15 Correct 363 ms 432 KB Output is correct
16 Correct 364 ms 344 KB Output is correct
17 Correct 335 ms 428 KB Output is correct
18 Runtime error 1 ms 348 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -