Submission #642771

#	Time	Username	Problem	Language	Result	Execution time	Memory
642771		dozer	Graph (BOI20_graph)	C++14	0 / 100	2 ms	4948 KiB

Graph

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
//#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define int long long

const int modulo = 1e9 + 7;

int ans[N], rev[N], sum, roott;
vector<int> adj[N];

int dfs(int node, int root)
{
	//cout<<node<<sp<<root<<endl;
	vector<int> v;
	for (auto i : adj[node])
	{
		if (i == root) continue;
		int res = dfs(i, node);
		if (res == 1) v.pb(i);
	}
	//cout<<node<<sp<<(int)v.size() - 1<<endl;
	for (int i = 0; i < ((int)v.size() - 1); i += 2)
	{
		//cout<<i<<sp<<"*"<<endl;
		ans[v[i]] = v[i + 1];
		ans[v[i + 1]] = v[i];
		sum += 4;
	}
	if (v.size() % 2 == 1)
	{
		ans[v.back()] = node;
		ans[node] = v.back();
		sum += 2;
		return 0;
	}
	if (node == roott)
	{
		if (v.size() == 0)
		{
			int x;
			for (auto i : adj[node]) if (i != root) x = i;
			v.pb(x);
			v.pb(ans[x]);
			sum += 2;
		}
		
		ans[node] = v[0];
		ans[v[0]] = v[1];
		ans[v[1]] = node;
		return 0;
	}
	return 1;
}


int32_t main()
{

	int n;
	cin>>n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin>>u>>v;
		adj[u].pb(v);
		adj[v].pb(u);
	}

	int mini = modulo, x = 0;
	roott = 1;
	for (int i = 1; i <= n; i++)
	{
		sum = 0;
		roott = i;
		int res = dfs(i, 0);
		if (sum < mini)
		{
			mini = sum;
			x = i;
		}
		//cout<<i<<sp<<sum<<endl;
	}
	
	sum = 0;
	roott = x;
	mini = dfs(x, 0);
	cout<<sum<<endl;
	for (int i = 1; i <= n; i++) cout<<ans[i]<<sp;
	cout<<endl;

	
	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Compilation message (stderr)

Graph.cpp: In function 'int32_t main()':
Graph.cpp:83:7: warning: unused variable 'res' [-Wunused-variable]
   83 |   int res = dfs(i, 0);
      |       ^~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 12
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 42