Submission #286271

#	Time	Username	Problem	Language	Result	Execution time	Memory
286271		spdskatr	Village (BOI20_village)	C++14	12 / 100	71 ms	384 KiB

Village

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cassert>

using namespace std;

int N;
int adj[15][15], p[15];
int minval = 2069696969, mina[15];
int maxval = 0, maxa[15];

int main() {
	scanf("%d", &N);
	assert(N <= 10);
	for (int i = 1; i <= N; i++) for (int j = i+1; j <= N; j++) adj[i][j] = adj[j][i] = 69;
	for (int i = 0; i < N-1; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		adj[a][b] = adj[b][a] = 1;
	}
	for (int m = 1; m <= N; m++)
		for (int u = 1; u <= N; u++)
			for (int v = 1; v <= N; v++)
				adj[u][v] = min(adj[u][v], adj[u][m] + adj[m][v]);
	for (int i = 1; i <= N; i++) p[i-1] = i;
	do {
		int val = 0, rip = 0;
		for (int i = 1; i <= N; i++) if (p[i-1] == i) {
			rip = 1;
		}
		if (rip) continue;
		for (int i = 1; i <= N; i++) val += adj[i][p[i-1]];
		if (val > maxval) {
			maxval = val;
			for (int i = 0; i < N; i++) maxa[i] = p[i];
		}
		if (val < minval) {
			minval = val;
			for (int i = 0; i < N; i++) mina[i] = p[i];
		}
	} while (next_permutation(p, p+N));
	printf("%d %d\n", minval, maxval);
	for (int i = 0; i < N; i++) {
		if (i == 0) printf("%d", mina[i]);
		else printf(" %d", mina[i]);
	} printf("\n");
	for (int i = 0; i < N; i++) {
		if (i == 0) printf("%d", maxa[i]);
		else printf(" %d", maxa[i]);
	} printf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:14:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Village.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%d %d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 38
• Subtask 3: 0 / 50