oj.uz

Submission #156133

# Submission time Handle Problem Language Result Execution time Memory
156133 2019-10-03T15:32:34 Z vex Mag (COCI16_mag) C++14
0 / 120
 682 ms 262148 KB 
#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];
			}
		}
	}
	
	dp[v][0][0]=manji(dp[v][0][0],{1,1});
	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];
		}
	}
}

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++)
	{
		for(int i=0;i<=Gre2;i++)
		{
			sol=manji(sol,dp[v][i][0]);
			for(int j=0;i+j<=Gre2+1 && 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;
				
				sol=manji(sol,tre);
			}
		}
	}
	
	ll d=__gcd(sol.gore,sol.dole);
	sol.gore/=d;
	sol.dole/=d;
	
	cout<<sol.gore<<"/"<<sol.dole;
	return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23800 KB Output is correct
2 Incorrect 26 ms 24184 KB Output isn't correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 24440 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 540 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 23800 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 606 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 682 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #7
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 660 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 548 ms 96396 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 622 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 650 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -