Submission #167563

#	Time	Username	Problem	Language	Result	Execution time	Memory
167563		manh9203	Mag (COCI16_mag)	C++17	120 / 120	552 ms	178272 KiB

mag

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int n,u,v,a[N],dp[N][2],ans1,ans2;
vector<int> adj[N];
void dfs(int u,int p){
	int mx1 = 0, mx2 = 0, mx3 = 0, mx4 = 0;
	int luu1 = -1, luu2 = -1, luu3 = -1, luu4 = -1;
	for(int v: adj[u]){
		if(v != p){
			dfs(v, u);
			if(dp[v][0] > mx1){
				mx2 = mx1;
				luu2 = luu1;
				mx1 = dp[v][0];
				luu1 = v;
			}else{
				if(dp[v][0] > mx2){
					mx2 = dp[v][0];
					luu2 = v;
				}
			}
			if(dp[v][1] > mx3){
				mx4 = mx3;
				luu4 = luu3;
				mx3 = dp[v][1];
				luu3 = v;
			}else{
				if(dp[v][1] > mx4){
					mx4 = dp[v][1];
					luu4 = v;
				}
			}
		}
	}
	if(a[u] == 1){
		ans1 = max(ans1, mx1 + mx2 + 1);
		if(luu1 != luu3){
			ans2 = max(ans2, mx1 + mx3 + 1);
		}else{
			ans2 = max(ans2, max(mx1 + mx4, mx2 + mx3) + 1);
		}
		dp[u][0] = mx1 + 1;
		dp[u][1] = mx3 + 1;
	}else{
		if(a[u] == 2){
			ans2 = max(ans2, mx1 + mx2 + 1);
			dp[u][0] = 0;
			dp[u][1] = mx1 + 1;
		}else{
			dp[u][0] = dp[u][1] = 0;
		}
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i=1;i<n;i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);	
	}
	long long mn = 1e18;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		mn = min(mn, (long long)a[i]);
	}
	dfs(1, 1);
	long long tu = mn, mau = 1;
	if(mau < tu*ans1){
		tu = 1;
		mau = ans1;
	}
	if(2*mau < tu*ans2){
		tu = 2;
		mau = ans2;
	}
	long long gd = __gcd(tu, mau);
	tu /= gd; mau /= gd;
	cout << tu << '/' << mau;
}

Compilation message (stderr)

mag.cpp: In function 'void dfs(int, int)':
mag.cpp:8:17: warning: variable 'luu2' set but not used [-Wunused-but-set-variable]
  int luu1 = -1, luu2 = -1, luu3 = -1, luu4 = -1;
                 ^~~~
mag.cpp:8:39: warning: variable 'luu4' set but not used [-Wunused-but-set-variable]
  int luu1 = -1, luu2 = -1, luu3 = -1, luu4 = -1;
                                       ^~~~

• 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