oj.uz

Submission #310646

# Submission time Handle Problem Language Result Execution time Memory
310646 2020-10-07T14:25:09 Z shivensinha4 Mag (COCI16_mag) C++17
120 / 120
 535 ms 82296 KB 
#include <bits/stdc++.h> 
using namespace std; 
#define for_(i, s, e) for (int i = s; i < (int) e; i++)
#define for__(i, s, e) for (ll i = s; i < e; i++)
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
#define endl '\n'
 
const int MXN = 1e6;
const ll INF = 1e17;
vi adj[MXN+1];
int chain[MXN+1], val[MXN+1], n;
pair<ll, ll> ans = {INF, 1};
 
void update(ll nu, ll de) {
	ll g = __gcd(nu, de);
	pair<ll, ll> temp = {nu/g, de/g};
	if (ans.first == INF) ans = temp;
	else if (temp.first*ans.second < ans.first*temp.second) ans = temp;
}
 
 
void dfs(int p, int parent) {
	stack<ii> s, ss;
	s.push({p, parent}); ss.push({p, parent});
	while (s.size()) {
		p = s.top().first, parent = s.top().second; s.pop();
		for (int i: adj[p]) if (i != parent) {
			s.push({i, p});
			ss.push({i, p});
		}
	}
	
	while (ss.size()) {
		p = ss.top().first, parent = ss.top().second; ss.pop();
		for (int i: adj[p]) if (i != parent) {
			chain[p] = max(chain[p], chain[i]);
		}
		if (val[p] == 1) chain[p] += 1;
		else chain[p] = 0;
	}
}
 
 
void dfs2(int p, int parent, int pval) {
	stack<vi> s;
	s.push({p, parent, pval});
	while (s.size()) {
		p = s.top()[0], parent = s.top()[1], pval = s.top()[2]; s.pop();
		vi mx(2);
		mx[0] = pval;
		for (int i: adj[p]) if (i != parent) {
			if (chain[i] >= mx[0]) mx = {chain[i], mx[0]};
			else mx[1] = max(mx[1], chain[i]);
		}
		
		update(val[p], mx[0]+mx[1]+1);
		
		for (auto i: adj[p]) if (i != parent) s.push({i, p, val[p] == 1 ? max(pval, mx[0] == chain[i] ? mx[1] : mx[0])+1 : 0});
 
	}
}
 
 
int main() {
	#ifdef shiven
	freopen("test.in", "r", stdin);
	#endif
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	for_(i, 0, n-1) {
		int a, b; cin >> a >> b;
		a -= 1; b -= 1;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	for_(i, 0, n) cin >> val[i];
	
	dfs(0, 0);
	dfs2(0, 0, 0);
	cout << ans.first << "/" << ans.second << endl;
 
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23936 KB Output is correct
2 Correct 17 ms 23936 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 18 ms 23936 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 58744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 23808 KB Output is correct
2 Correct 520 ms 66976 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 517 ms 66348 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 67100 KB Output is correct
2 Correct 388 ms 55548 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 82296 KB Output is correct
2 Correct 113 ms 28664 KB Output is correct
3 Correct 518 ms 67464 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 28664 KB Output is correct
2 Correct 528 ms 67080 KB Output is correct
3 Correct 503 ms 46456 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 491 ms 65036 KB Output is correct
2 Correct 530 ms 66612 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 532 ms 67592 KB Output is correct
2 Correct 483 ms 46584 KB Output is correct