oj.uz

Submission #953495

# Submission time Handle Problem Language Result Execution time Memory
953495 2024-03-26T03:39:17 Z koukirocks Village (BOI20_village) C++17
12 / 100
 417 ms 600 KB 
#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#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) {
//	cout<<v<<" "<<p<<"\n"<<flush;
	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() {
	speed;
	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;
		}
		{
//			for (int i=1;i<=n;i++) {
//				cout<<perm[i]<<" ";
//			}
//			cout<<"\n"<<flush;
			int ttl=0;
			for (int i=1;i<=n;i++) {
				ttl+=dfs(i,0,0,perm[i]);
			}
//			cout<<ttl<<" ttl\n"<<flush;
			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";
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 452 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 500 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 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 30 ms 348 KB Output is correct
10 Correct 319 ms 600 KB Output is correct
11 Correct 361 ms 428 KB Output is correct
12 Correct 342 ms 436 KB Output is correct
13 Correct 372 ms 432 KB Output is correct
14 Correct 417 ms 348 KB Output is correct
15 Correct 362 ms 592 KB Output is correct
16 Correct 376 ms 348 KB Output is correct
17 Correct 326 ms 596 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 0 ms 452 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 456 KB Output is correct
4 Correct 1 ms 500 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 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 30 ms 348 KB Output is correct
10 Correct 319 ms 600 KB Output is correct
11 Correct 361 ms 428 KB Output is correct
12 Correct 342 ms 436 KB Output is correct
13 Correct 372 ms 432 KB Output is correct
14 Correct 417 ms 348 KB Output is correct
15 Correct 362 ms 592 KB Output is correct
16 Correct 376 ms 348 KB Output is correct
17 Correct 326 ms 596 KB Output is correct
18 Runtime error 1 ms 348 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -