# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
201157 | SamAnd | Mag (COCI16_mag) | C++17 | 635 ms | 158572 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int N = 1000006;
int gcd(int x, int y)
{
while (y)
{
x %= y;
swap(x, y);
}
return x;
}
struct ban
{
int x, y;
ban()
{
x = 0;
y = 1;
}
ban(int x, int y)
{
int g = gcd(x, y);
this->x = x / g;
this->y = y / g;
}
};
bool operator<(const ban& a, const ban& b)
{
return (a.x * 1LL * b.y) < (b.x * 1LL * a.y);
}
int n;
vector<int> a[N];
int u[N];
int q[N];
void dfs(int x, int p)
{
if (u[x] == 1)
q[x] = 1;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
dfs(h, x);
if (u[x] == 1)
q[x] = max(q[x], q[h] + 1);
}
}
ban ans;
void dfs1(int x, int p, int qp)
{
int max1 = qp;
int max2 = 0;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (q[h] >= max1)
{
max2 = max1;
max1 = q[h];
}
else if (q[h] >= max2)
max2 = q[h];
}
ban t = ban(u[x], max1 + 1 + max2);
if (t < ans)
ans = t;
for (int i = 0; i < a[x].size(); ++i)
{
int h = a[x][i];
if (h == p)
continue;
if (u[x] == 1)
{
if (q[h] == max1)
dfs1(h, x, max2 + 1);
else
dfs1(h, x, max1 + 1);
}
else
dfs1(h, x, 0);
}
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n - 1; ++i)
{
int x, y;
scanf("%d%d", &x, &y);
a[x].push_back(y);
a[y].push_back(x);
}
for (int i = 1; i <= n; ++i)
scanf("%d", &u[i]);
dfs(1, 1);
ans = ban(u[1], 1);
dfs1(1, 1, 0);
printf("%d/%d\n", ans.x, ans.y);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |