Submission #679227

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
679227	2023-01-07T19:26:11 Z	ziduo	Mag (COCI16_mag)	C++14	96 / 120	436 ms	141148 KB

#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 = 1;
        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

mag.cpp: In function 'void dfs(int, int)':
mag.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < a[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
mag.cpp: In function 'void dfs1(int, int, int)':
mag.cpp:60:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for (int i = 0; i < a[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
mag.cpp:76:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for (int i = 0; i < a[x].size(); ++i)
      |                     ~~^~~~~~~~~~~~~
mag.cpp: In function 'int main()':
mag.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
mag.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   99 |         scanf("%d%d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~
mag.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d", &u[i]);
      |         ~~~~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	11 ms	23764 KB	Output is correct
2	Correct	12 ms	23764 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	23764 KB	Output is correct
2	Incorrect	12 ms	23804 KB	Output isn't correct
3	Halted	0 ms	0 KB	-

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	344 ms	86364 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	12 ms	23764 KB	Output is correct
2	Correct	436 ms	140324 KB	Output is correct

Subtask #5
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	428 ms	138456 KB	Output is correct

Subtask #6
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	364 ms	62676 KB	Output is correct
2	Correct	269 ms	52536 KB	Output is correct

Subtask #7
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	361 ms	63892 KB	Output is correct
2	Correct	60 ms	27744 KB	Output is correct
3	Correct	424 ms	141148 KB	Output is correct

Subtask #8
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	27756 KB	Output is correct
2	Correct	366 ms	63184 KB	Output is correct
3	Correct	280 ms	43804 KB	Output is correct

Subtask #9
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	327 ms	60668 KB	Output is correct
2	Correct	361 ms	62156 KB	Output is correct

Subtask #10
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	379 ms	63308 KB	Output isn't correct
2	Halted	0 ms	0 KB	-