| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 80544 |
2018-10-21T09:58:09 Z |
pzdba |
Mag (COCI16_mag) |
C++14 |
|
878 ms |
263168 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef long double LD;
typedef pair<LL, LL> pll;
vector<int> g[1000005];
LL x[1000005];
pll ans;
pll dp[1000005];
LL gcd[1000005];
bool cmp(pll a, pll b){
return (LD)a.first*b.second < (LD)b.first*a.second;
}
void dfs(int u, int p){
vector<pll> mn;
dp[u] = pll(x[u], 1);
int cnt = 0;
for(int i=0;i<g[u].size();i++){
int v = g[u][i];
if(v == p) continue;
cnt++;
dfs(v, u);
LL d1 = dp[v].first, d2 = dp[v].second;
d1 *= gcd[v];
d2 *= gcd[v];
mn.push_back(pll(d1, d2));
}
sort(mn.begin(), mn.end(), cmp);
if(cnt == 0){
dp[u] = pll(x[u], 1);
}
else if(cnt == 1){
LL d1 = mn[0].first, d2 = mn[0].second;
if((LD)d1*x[u] <= 2e18){
d1 *= x[u];
d2++;
LL gc = __gcd(d1, d2);
d1 /= gc;
d2 /= gc;
if(cmp(pll(d1, d2), dp[u])) dp[u] = pll(d1, d2), gcd[u] = gc;
}
}
else{
LL d1 = mn[0].first, d2 = mn[0].second;
LL e1 = mn[1].first, e2 = mn[1].second;
if((LD)d1*x[u] <= 2e18){
d1 *= x[u];
d2++;
LL gc = __gcd(d1, d2);
d1 /= gc;
d2 /= gc;
if(cmp(pll(d1, d2), dp[u])) dp[u] = pll(d1, d2), gcd[u] = gc;
d1 *= gc;
d2 *= gc;
if((LD)d1*e1 <= 2e18){
d1 *= e1;
d2 += e2;
LL gc = __gcd(d1, d2);
if(cmp(pll(d1, d2), ans)) ans = pll(d1, d2);
}
}
}
if(cmp(dp[u], ans)) ans = dp[u];
}
int main(){
ans.first = 1e18, ans.second = 1;
int n;
scanf("%d", &n);
for(int i=1;i<=n-1;i++){
int a, b;
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for(int i=1;i<=n;i++){
scanf("%lld", &x[i]);
ans.first = min(ans.first, x[i]);
gcd[i] = 1;
}
dfs(1, 0);
LL g = __gcd(ans.first, ans.second);
ans.first /= g;
ans.second /= g;
printf("%lld/%lld\n", ans.first, ans.second);
}
Compilation message
mag.cpp: In function 'void dfs(int, int)':
mag.cpp:18:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++){
~^~~~~~~~~~~~
mag.cpp:59:8: warning: unused variable 'gc' [-Wunused-variable]
LL gc = __gcd(d1, d2);
^~
mag.cpp: In function 'int main()':
mag.cpp:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &n);
~~~~~^~~~~~~~~~
mag.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~
mag.cpp:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld", &x[i]);
~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
24056 KB |
Output is correct |
| 2 |
Correct |
23 ms |
24140 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
27 ms |
24336 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
621 ms |
144676 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
144676 KB |
Output is correct |
| 2 |
Incorrect |
763 ms |
255196 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
878 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
720 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
651 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
117 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
595 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
670 ms |
263168 KB |
Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience. |
| 2 |
Halted |
0 ms |
0 KB |
- |
