Submission #1044711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044711		goodspeed0208	Village (BOI20_village)	C++14	50 / 100	68 ms	21216 KiB

Village

#include<bits/stdc++.h>
#define int long long
#define pii pair<long long, long long>
using namespace std;

int n, minn = 0, maxx = 0;
vector<vector<int> >G;
vector<int>minans;
vector<int>maxans;

bool dfs(int x, int p) {
	vector<int>c;
	for (auto i : G[x]) {
		if (i == p) continue;
		bool can = dfs(i, x);
		if (can) {
			c.push_back(i);
		}
	}
	//cout << x <<" " << c.size() << "\n";
	for (int i = 0 ; i < c.size()/2 ; i++) {
		minn += 4;
		minans[c[i*2]] = i*2+1;
		minans[c[i*2+1]] = i*2;
	}
	if (c.size() % 2 == 1) {
		minn += 2;
		minans[c.back()] = x;
		minans[x] = c.back();
		return 0;
	} else {
		if (x == 0) {
			minn += 2;
			minans[x] = minans[G[x][0]];
			minans[G[x][0]] = x;
			return 0;
		}
		return 1;
	}
}

int cnt;

int findc(int x, int p) {
	int num = 1;
	bool can = 1;
	for (auto i : G[x]) {
		if (i == p) continue;
		int child = findc(i, x);
		if (child > n/2) can = 0;
		num += child;
	}
	if (n - num > n/2) can = 0;
	if (can) cnt = x;
	return num;
}

vector<int>arr;

void dis(int x, int p, int d) {
	maxx += d*2;
	arr.push_back(x);
	for (auto i : G[x]) {
		if (i == p) continue;
		dis(i, x, d+1);
	}
}

signed main() {
	cin >> n;
	G.resize(n); minans.resize(n); maxans.resize(n);
	int a, b;
	for (int i = 0 ; i < n-1 ; i++){
		cin >> a >> b; a--, b--;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	dfs(0, -1);
	findc(0, -1);
	dis(cnt, -1, 0);
	for (int i = 0 ; i < n ; i++) {
		//cout << arr[i] <<" ";
		maxans[arr[i]] = arr[(i+n/2)%n];
	}
	//cout <<"\n";
	cout << minn << " " << maxx << "\n";
	for (auto i : minans) cout << i+1 << " "; cout << "\n";
	for (auto i : maxans) cout << i+1 << " "; cout << "\n";
}

Compilation message (stderr)

Village.cpp: In function 'bool dfs(long long int, long long int)':
Village.cpp:21:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for (int i = 0 ; i < c.size()/2 ; i++) {
      |                   ~~^~~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:87:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   87 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:87:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   87 |  for (auto i : minans) cout << i+1 << " "; cout << "\n";
      |                                            ^~~~
Village.cpp:88:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   88 |  for (auto i : maxans) cout << i+1 << " "; cout << "\n";
      |  ^~~
Village.cpp:88:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   88 |  for (auto i : maxans) cout << i+1 << " "; cout << "\n";
      |                                            ^~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50