oj.uz

Submission #642771

# Submission time Handle Problem Language Result Execution time Memory
642771 2022-09-20T13:20:09 Z dozer Graph (BOI20_graph) C++14
0 / 100
 2 ms 4948 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Expected YES or NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Expected YES or NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Expected YES or NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Expected YES or NO
2 Halted 0 ms 0 KB -

Subtask #5
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4948 KB Expected YES or NO
2 Halted 0 ms 0 KB -