# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
310609 |
2020-10-07T13:45:43 Z |
shivensinha4 |
Mag (COCI16_mag) |
C++17 |
|
737 ms |
250892 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};
assert(temp.first <= INF);
if (ans.first == INF and temp.first <= INF) ans = temp;
else {
pair<ll, ll> pre = ans, pree = temp;
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;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
24064 KB |
Output is correct |
2 |
Correct |
17 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
23936 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
537 ms |
130296 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23808 KB |
Output is correct |
2 |
Correct |
714 ms |
248820 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
713 ms |
245368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
576 ms |
62968 KB |
Output is correct |
2 |
Correct |
423 ms |
53076 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
540 ms |
67048 KB |
Output is correct |
2 |
Correct |
106 ms |
27896 KB |
Output is correct |
3 |
Correct |
737 ms |
250892 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
27896 KB |
Output is correct |
2 |
Correct |
604 ms |
64588 KB |
Output is correct |
3 |
Correct |
518 ms |
43896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
523 ms |
62924 KB |
Output is correct |
2 |
Correct |
580 ms |
62476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
577 ms |
63992 KB |
Output is correct |
2 |
Correct |
522 ms |
43896 KB |
Output is correct |