oj.uz

Submission #310607

# Submission time Handle Problem Language Result Execution time Memory
310607 2020-10-07T13:44:22 Z shivensinha4 Mag (COCI16_mag) C++17
108 / 120
 768 ms 250812 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 val[MXN+1];
int chain[MXN+1];
int 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 and temp.first <= INF) ans = temp;
	else {
		pair<ll, ll> pre = ans, pree = temp;
		//ll lcm = temp.second * (pre.second / __gcd(temp.second, pre.second));
		temp.first *= pre.second, pre.first *= temp.second;
		if (temp.first < pre.first) ans = pree;
	}
}


void dfs(int p, int parent) {
	for (int i: adj[p]) if (i != parent) {
		dfs(i, p);
		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) {
	vi all, mx(2);
	all.push_back(pval);
	for (int i: adj[p]) if (i != parent) all.push_back(chain[i]);
	sort(all.begin(), all.end(), greater<int>());
	for_(i, 0, min((int) all.size(), 2)) mx[i] = all[i];
	
	update(val[p], mx[0]+mx[1]+1);
	
	for (auto i: adj[p]) if (i != parent) dfs2(i, p, val[p] == 1 ? pval+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 23808 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 534 ms 130424 KB Output isn't correct

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 717 ms 245300 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 552 ms 63096 KB Output is correct
2 Correct 430 ms 52964 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 560 ms 67004 KB Output is correct
2 Correct 114 ms 27900 KB Output is correct
3 Correct 768 ms 250812 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 27900 KB Output is correct
2 Correct 588 ms 64376 KB Output is correct
3 Correct 502 ms 43896 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 62956 KB Output is correct
2 Correct 552 ms 62288 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 63992 KB Output is correct
2 Correct 534 ms 43896 KB Output is correct