# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
331470 |
2020-11-28T15:23:58 Z |
BeanZ |
Mag (COCI16_mag) |
C++14 |
|
453 ms |
157096 KB |
// I_Love_LPL
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int lim = 100;
ll a[N];
vector<ll> node[N];
pair<ll, ll> dp[N];
bool cmp(ll x, ll y){
return ((dp[x].first * dp[y].second) < (dp[x].second * dp[y].first));
}
pair<ll, ll> mul(pair<ll, ll> x, pair<ll, ll> y){
return {x.first * y.first, x.second + y.second};
}
pair<ll, ll> cal(pair<ll, ll> x, pair<ll, ll> y){
if ((x.first * y.second) <= (x.second * y.first)) return x;
else return y;
}
pair<ll, ll> ans = {1e9, 1};
void dfs(ll u, ll p){
dp[u] = {a[u], 1};
for (auto j : node[u]){
if (j == p) continue;
dfs(j, u);
}
for (int i = 0; i < node[u].size(); i++){
if (node[u][i] == p){
swap(node[u][i], node[u][node[u].size() - 1]);
node[u].pop_back();
break;
}
}
sort(node[u].begin(), node[u].end(), cmp);
ans = cal(ans, dp[u]);
if (node[u].size()){
ll can1 = node[u][0];
dp[u] = cal(mul(dp[u], dp[can1]), dp[u]);
ans = cal(ans, dp[u]);
if (node[u].size() >= 2){
ll can2 = node[u][1];
ans = cal(ans, mul(dp[u], dp[can2]));
}
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
if (fopen("A.inp", "r")){
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
ll n;
cin >> n;
for (int i = 1; i < n; i++){
ll u, v;
cin >> u >> v;
node[u].push_back(v);
node[v].push_back(u);
}
for (int i = 1; i <= n; i++) cin >> a[i];
dfs(1, 1);
ll gcd = __gcd(ans.first, ans.second);
ans.first /= gcd;
ans.second /= gcd;
cout << ans.first << "/" << ans.second << endl;
}
/*
5
1 2
2 4
1 3
5 2
2
1
1
1
3
*/
Compilation message
mag.cpp: In function 'void dfs(long long int, long long int)':
mag.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
29 | for (int i = 0; i < node[u].size(); i++){
| ~~^~~~~~~~~~~~~~~~
mag.cpp: In function 'int main()':
mag.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
52 | freopen("test.inp", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
mag.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
53 | freopen("test.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23916 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23936 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
347 ms |
99292 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
444 ms |
153736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
386 ms |
78444 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
401 ms |
80648 KB |
Output is correct |
2 |
Correct |
94 ms |
30060 KB |
Output is correct |
3 |
Correct |
453 ms |
157096 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
81 ms |
30060 KB |
Output is correct |
2 |
Incorrect |
403 ms |
79116 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
365 ms |
75232 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
410 ms |
79212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |