Submission #156132

#	Time	Username	Problem	Language	Result	Execution time	Memory
156132		vex	Mag (COCI16_mag)	C++14	12 / 120	667 ms	262148 KiB

mag

#include <bits/stdc++.h>
#define maxn 1000005
#define INF 2000000000
#define ll long long
#define pll pair<ll,ll>
#define gore first
#define dole second
#define qINF {maxn,1}
using namespace std;

const int Gre2 = 20;

int n;
int a[maxn];
vector<int>adj[maxn];

pll manji(pll q1,pll q2)
{
	bool t=(q1.gore*q2.dole<=q2.gore*q1.dole);
	
	if(t)return q1;
	return q2;
}

pll dp[maxn][22][2];
void dfs(int v,int p)
{
	for(int i=0;i<=Gre2;i++)
	{
		dp[v][i][0]=dp[v][i][1]=qINF;
	}
	for(auto x:adj[v])
	{
		if(x==p)continue;
		
		dfs(x,v);
		
		for(int i=0;i<=Gre2;i++)
		{
			if( manji(dp[v][i][0],dp[x][i][0])==dp[x][i][0] )
			{
				dp[v][i][1]=dp[v][i][0];
				dp[v][i][0]=dp[x][i][0];
			}
			else if( manji(dp[v][i][1],dp[x][i][0])==dp[x][i][0] )
			{
				dp[v][i][1]=dp[x][i][0];
			}
		}
	}
	
	
	for(int i=0;i<=Gre2;i++)
	{
		dp[v][i][0].dole++;
		dp[v][i][1].dole++;
		
		dp[v][i][0].gore*=a[v];
		dp[v][i][1].gore*=a[v];
		
		if(dp[v][i][0].gore>=dp[v][i][0].dole)dp[v][i][0]=qINF;
		if(dp[v][i][1].gore>=dp[v][i][1].dole)dp[v][i][1]=qINF;
	}
	
	if (a[v]!=1)
	{
		dp[v][0][0]=qINF;
		dp[v][0][1]=qINF;
		
		for(int i=Gre2;i>0;i--)
		{
			dp[v][i][0]=dp[v][i-1][0];
			dp[v][i][1]=dp[v][i-1][1];
		}
	}
	else
	{
		dp[v][0][0]=manji(dp[v][0][0],{1,1});
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	int najm=INF;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		najm=min(a[i],najm);
	}
	
	if(najm>1)
	{
		cout<<najm<<"/1";
		return 0;
	}
	
	dfs(1,1);
	
	
	pll sol={1,1};
	for(int v=1;v<=n;v++)
	{
		//cout<<v<<"  ";
		for(int i=0;i<=Gre2;i++)
		{
			//cout<<dp[v][i][0].gore<<"/"<<dp[v][i][0].dole<<","<<dp[v][i][1].gore<<"/"<<dp[v][i][1].dole<<" ";
			sol=manji(sol,dp[v][i][0]);
			for(int j=0;i+j<=Gre2;j++)
			{
				int ind1=0,ind2=0;
				if(i==j)ind2=1;
				
				pll tre;
				tre.gore=dp[v][i][ind1].gore*dp[v][j][ind2].gore/a[v];
				tre.dole=dp[v][i][ind1].dole+dp[v][j][ind2].dole-1;
				
				if(tre.gore>=tre.dole)continue;
				
				/*if(manji(sol,tre)==tre)
				{
					cout<<i<<","<<j<<","<<tre.gore<<"/"<<tre.dole<<",";
					cout<<dp[v][i][ind1].gore<<"/"<<dp[v][i][ind1].dole<<",";
					cout<<dp[v][j][ind2].gore<<"/"<<dp[v][j][ind2].dole<<endl;
				}*/
				sol=manji(sol,tre);
			}
		}
		//cout<<endl;
	}
	
	ll d=__gcd(sol.gore,sol.dole);
	sol.gore/=d;
	sol.dole/=d;
	
	cout<<sol.gore<<"/"<<sol.dole;
	return 0;
}

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