Submission #1102058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102058		NDT134	Village (BOI20_village)	C++14	25 / 100	398 ms	262144 KiB

Village

#include<iostream>
#include<vector>
#include<queue>
#include<map>
using namespace std;

int main() {
	int n; cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++)
	{
		int x, y, z; cin >> x >> y; x--; y--;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	vector<int> p(n), c(n);
	queue<int> q; q.push(0);
	while (!q.empty())
	{
		int x = q.front(); q.pop();
		for (int y : g[x])
		{
			if (p[x] != y)
			{
				p[y] = x;
				q.push(y);
				c[x]++;
			}
		}
	}

	for (int i = 0; i < n; i++)
	{
		if (!c[i])
		{
			q.push(i);
		}
	}
	vector<int> a(n), b(n), rm(n);
	vector<map<int,int>> m(n);
	while (!q.empty())
	{
		vector<int> v;
		int x = q.front(); q.pop();
		c[p[x]]--;
		if (!c[p[x]])
		{
			q.push(p[x]);
		}
		for (int y : g[x])
		{
			if (p[x] != y)
			{
				v.push_back(y);
			}
		}

		if (v.empty())
		{
			b[x] = 0;
			a[x] = -1;
			continue;
		}

		int k = 0, s = 0;
		vector<int> u;
		for (int y : v)
		{
			if (a[y] == -1)
			{
				k++;
				u.push_back(y);
			}
			else
			{
				s += a[y];
			}
		}

		int z = v[rand() % v.size()];
		m[x] = m[z];
		if (k > 0)
		{
			a[x] = s + 2 * k;
			b[x] = a[x];
			for (int y : v)
			{
				if (a[y] != -1 && y != z)
				{
					for (map<int, int>::const_iterator it = m[y].begin(); it != m[y].end(); ++it)
					{
						m[x][it->first] = it->second;
					}
				}
			}
			u.push_back(x);
			int l = u.size();
			for (int i = 0; i < l; i++)
			{
				m[x][u[i]] = u[(i + 1) % l];
			}
			rm[x] = u[u.size() - 2];
			continue;
		}
		
		b[x] = s;
		bool bb = 1;
		int t = -1;
		for (int y : v)
		{
			if (b[y] != a[y])
			{
				t = y;
			}
		}
		for (int y : v)
		{
			if (y != z)
			{
				for (map<int, int>::const_iterator it = m[y].begin(); it != m[y].end(); ++it)
				{
					m[x][it->first] = it->second;
				}
			}
		}
		a[x] = b[x] + 2 * (t == -1);
		if (t != -1)
		{
			m[x][rm[t]] = m[t][t];
			m[x][x] = t;
			m[x][t] = x;
			rm[x] = t;
			continue;
		}
		
		t = v[0];
		m[x][rm[t]] = x;
		m[x][x] = t;
		rm[x] = rm[t];
	}

	cout << a[0] << " " << 0 << endl;
	for (int i = 0; i < n; i++)
	{
		cout << m[0][i] + 1 << " ";
	}
	cout << endl;
	for (int i = 0; i < n; i++)
	{
		cout << 1 << " ";
	}
	cout << endl;
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:12:13: warning: unused variable 'z' [-Wunused-variable]
   12 |   int x, y, z; cin >> x >> y; x--; y--;
      |             ^
Village.cpp:107:8: warning: unused variable 'bb' [-Wunused-variable]
  107 |   bool bb = 1;
      |        ^~

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