Submission #256453

#	Time	Username	Problem	Language	Result	Execution time	Memory
256453		ElyesChaabouni	Mag (COCI16_mag)	C++14	120 / 120	612 ms	83836 KiB

mag

#include<bits/stdc++.h>
#define eps 1e-9
#define MOD1 998244353
#define MOD2 1000000007
#define INV_10 299473306
#define INF 1000000001
#define PI 3.14159265358979323846
using namespace std;
vector<pair<int, int> >v[1000005];
int a[1000005];
pair<long long, long long>mi(pair<long long, long long>x, pair<long long , long long>y)
{
	if(x.first*y.second <= y.first*x.second)
		return x;
	return y;
}
int dfs(int idx, int anc)
{
	if(a[idx]!=1)
		return 0;
	int cu=0;
	for(int i = 0; i < v[idx].size(); i++)
	{
		if(v[idx][i].first!=anc)
		{
			if(v[idx][i].second==-1)
				v[idx][i].second=dfs(v[idx][i].first, idx);
			cu=max(cu, v[idx][i].second);
		}
	}
	cu++;
	return cu;
}
pair<int, int>get_val(int idx)
{
	if(a[idx]> 2)
		return make_pair(a[idx], 1);
	vector<int>cu;
	for(int i = 0; i < v[idx].size(); i++)
	{
		if(v[idx][i].second==-1)
			v[idx][i].second=dfs(v[idx][i].first, idx);
		cu.push_back(v[idx][i].second);
	}
	sort(cu.begin(), cu.end());
	reverse(cu.begin(), cu.end());
	if(a[idx]==1)
	{
		if(cu.size()==1)
			return make_pair(1, cu[0]+1);
		return make_pair(1, cu[0]+cu[1]+1);
	}
	if(cu.size()==1)
		return make_pair(2, 1);
	return make_pair(2, 2*min(cu[0],cu[1])+1);
}
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i < n-1; i++)
	{
		int x, y;
		cin >> x >> y;
		v[x].push_back(make_pair(y, -1));
		v[y].push_back(make_pair(x, -1));
	}
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	pair<long long, long long>ans=make_pair(1000000000LL, 1);
	for(int i = 1; i <= n; i++)
		ans=mi(ans, get_val(i));
	cout << ans.first << '/' << ans.second << '\n';
}

Compilation message (stderr)

mag.cpp: In function 'int dfs(int, int)':
mag.cpp:22:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[idx].size(); i++)
                 ~~^~~~~~~~~~~~~~~
mag.cpp: In function 'std::pair<int, int> get_val(int)':
mag.cpp:39:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < v[idx].size(); i++)
                 ~~^~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12