제출 #291903

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
291903		Berted	Village (BOI20_village)	C++14	100 / 100	258 ms	19700 KiB

Village

#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#define vi vector<int>
#define pub push_back
using namespace std;
 
int n;
vi adj[100001];
int res[100001], dp[100001][2];
int mtcW[100001];
int res2[100001], sub[100001];
long long k = 0;
vector<vi> ord;
 
void dfs(int u, int p)
{
	dp[u][0] = dp[u][1] = 0;
	int ret = 0;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			dfs(v, u);
			ret += dp[v][1];
		}
	}
	dp[u][0] = ret;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			assert(dp[v][1] >= dp[v][0]);
			dp[u][1] = max(dp[u][1], 1 + ret - dp[v][1] + dp[v][0]);
		}
	}
}
 
void bktrk(int u, int p, int s)
{
	if (dp[u][s] == 0 && res[u] == -1)
	{
		res[u] = res[p];
		res[p] = u;	
	}
	if (s)
	{
		int ret = 0, spc = -1;
		for (auto v : adj[u])
		{
			if (v != p) {ret += dp[v][1];}
		}
		for (auto v : adj[u])
		{
			if (v != p)
			{
				assert(dp[v][1] >= dp[v][0]);
				if (1 + ret - dp[v][1] + dp[v][0] == dp[u][1]) 
				{
					spc = v; 
					res[spc] = u;
					res[u] = spc;
					break;
				}
			}
		}
		for (auto v : adj[u])
		{
			if (v != p) bktrk(v, u, (spc != v));
		}
	}
	else
	{
		for (auto v : adj[u])
		{
			if (v != p) {bktrk(v, u, 1);}
		}
	}
}
 
void computeSub(int u, int p)
{
	sub[u] = 1;
	for (auto v : adj[u])
	{
		if (v != p)
		{
			computeSub(v, u);
			sub[u] += sub[v];
		}
	}
}
 
int findCentroid(int u, int p, int o)
{
	for (auto v : adj[u])
	{
		if (v != p && sub[v] > sub[o] / 2) return findCentroid(v, u, o);
	}
	return u;
}
 
void dfs2(int u, int p)
{
	sub[u] = 1;
	if (p == -1) ord.push_back(vi());
	ord.back().push_back(u);
	for (auto v : adj[u])
	{
		if (p == -1) ord.push_back(vi());
		if (v != p)
		{
			dfs2(v, u);
			sub[u] += sub[v];
			k += 2 * sub[v];
		}
	}
}
 
bool comp(const vi &a, const vi &b) {return a.size() < b.size();}
 
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++) res[i] = -1;
	for (int i = 1; i < n; i++)
	{
		int u, v; cin >> u >> v;
		adj[u - 1].push_back(v - 1);
		adj[v - 1].push_back(u - 1);
	}
 
	dfs(0, -1);
	bktrk(0, -1, 1);
  
  	computeSub(0, -1);
	int c = findCentroid(0, -1, 0);
	dfs2(c, -1);
 
	sort(ord.begin(), ord.end(), comp);
 
	int j = ord.size() - 1, p = 0;
	for (int i = 0; i < ord.size(); i++)
	{
		for (int i2 = 0; i2 < ord[i].size(); i2++)
		{
			res2[ord[i][i2]] = ord[j][p++];
			if (p == ord[j].size()) {j = (j + 1) % ord.size(); p = 0;}
		}
	}
  
	cout << 2 * (dp[0][1] + n - 2 * dp[0][1]) << " " << k << "\n";
	
	for (int i = 0; i < n; i++)
	{
		cout << res[i] + 1;
		if (i + 1 < n) cout << " ";
	}
  	cout << "\n";
  	for (int i = 0; i < n; i++)
	{
		cout << res2[i] + 1;
		if (i + 1 < n) cout << " ";
	}
  	cout << "\n";
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Village.cpp: In function 'int main()':
Village.cpp:144:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for (int i = 0; i < ord.size(); i++)
      |                  ~~^~~~~~~~~~~~
Village.cpp:146:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |   for (int i2 = 0; i2 < ord[i].size(); i2++)
      |                    ~~~^~~~~~~~~~~~~~~
Village.cpp:149:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  149 |    if (p == ord[j].size()) {j = (j + 1) % ord.size(); p = 0;}
      |        ~~^~~~~~~~~~~~~~~~

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