oj.uz

Submission #167563

# Submission time Handle Problem Language Result Execution time Memory
167563 2019-12-09T02:10:29 Z manh9203 Mag (COCI16_mag) C++17
120 / 120
 552 ms 178272 KB 
#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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 23928 KB Output is correct
2 Correct 23 ms 23796 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23928 KB Output is correct
2 Correct 23 ms 23928 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 96504 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 23800 KB Output is correct
2 Correct 547 ms 174836 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 540 ms 161804 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 470 ms 67556 KB Output is correct
2 Correct 348 ms 66652 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 68932 KB Output is correct
2 Correct 85 ms 29944 KB Output is correct
3 Correct 552 ms 178272 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 29556 KB Output is correct
2 Correct 461 ms 68704 KB Output is correct
3 Correct 341 ms 53704 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 65560 KB Output is correct
2 Correct 451 ms 67644 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 480 ms 68508 KB Output is correct
2 Correct 359 ms 47240 KB Output is correct