# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
310615 |
2020-10-07T13:52:25 Z |
shivensinha4 |
Mag (COCI16_mag) |
C++17 |
|
740 ms |
251000 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) {
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);
assert(ans.first != INF);
cout << ans.first << "/" << ans.second << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23936 KB |
Output is correct |
2 |
Correct |
16 ms |
23936 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23808 KB |
Output is correct |
2 |
Correct |
16 ms |
23948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
566 ms |
130280 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
23936 KB |
Output is correct |
2 |
Correct |
740 ms |
248836 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
681 ms |
245496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
547 ms |
62840 KB |
Output is correct |
2 |
Correct |
410 ms |
53112 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
522 ms |
66916 KB |
Output is correct |
2 |
Correct |
107 ms |
27896 KB |
Output is correct |
3 |
Correct |
703 ms |
251000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
27896 KB |
Output is correct |
2 |
Correct |
542 ms |
64376 KB |
Output is correct |
3 |
Correct |
474 ms |
43896 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
492 ms |
62960 KB |
Output is correct |
2 |
Correct |
530 ms |
62328 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
554 ms |
63992 KB |
Output is correct |
2 |
Correct |
473 ms |
44024 KB |
Output is correct |