Submission #805285

#	Time	Username	Problem	Language	Result	Execution time	Memory
805285		tlnk07	Papričice (COCI20_papricice)	C++17	0 / 110	44 ms	724 KiB

papricice

#include<bits/stdc++.h>
using namespace std;

long long n, x, y, cnt, pos, check = 0, c[20001], t, mini = INT_MAX;
vector<int> vec[20001];

void dfs(int x, int p, int done)
{
	if(x == done)	return;
	++cnt;
	for(int c : vec[x])	if(c != p)	dfs(c, x, done);
}
void dfs2(int x, int p, int done, int done2)
{
	if(x == done)
	{
		return;
		check = 1;
	}	
	++cnt;
	for(int c : vec[x])
	{
		cnt = 0;
		if(c != p)	dfs(c, x, done);
		if(check && x == done2)	return;
	}	
}

int main()
{
	cin >> n;
	for(int i = 1; i < n; ++i)
	{
		cin >> x >> y;
		vec[x].push_back(y);
		vec[y].push_back(x);
	}
	for(int i = 1; i <= n; ++i)
	{
		for(int j = i + 1; j <= n; ++j)
		{
			cnt = 0;
			dfs(i, 0, j);
			long long temp = cnt;
			cnt = 0;
			dfs(j, 0, i);
			long long temp2 = cnt;
			cnt = 0;
			dfs2(i, 0, j, i);
			temp -= cnt;
			temp2 -= cnt;
			mini = min(mini, max(abs(temp - temp2), max(abs(temp - cnt), abs(temp2 - cnt))));
		}
	}
	cout << mini;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60