oj.uz

답안 #201152

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
201152 2020-02-09T13:06:55 Z SamAnd Mag (COCI16_mag) C++17
84 / 120
 903 ms 262148 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 = 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)
{
    multiset<int> s;
    s.insert(qp);
    s.insert(0);
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        s.insert(q[h]);
    }
    ban t = ban(u[x], *(--s.end()) + 1 + *(--(--s.end())));
    if (t < ans)
        ans = t;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        s.erase(s.find(q[h]));
        if (u[x] == 1)
            dfs1(h, x, *(--s.end()) + 1);
        else
            dfs1(h, x, 0);
        s.insert(q[h]);
    }
}

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 between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mag.cpp: In function 'void dfs1(int, int, int)':
mag.cpp:61:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mag.cpp:71:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
mag.cpp: In function 'int main()':
mag.cpp:87:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
mag.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
mag.cpp:96:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &u[i]);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23928 KB Output is correct
2 Correct 19 ms 23800 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23800 KB Output is correct
2 Correct 19 ms 23932 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 742 ms 163024 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 19 ms 23804 KB Output is correct
2 Runtime error 903 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 840 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #6
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 743 ms 78200 KB Output is correct
2 Correct 555 ms 64376 KB Output is correct

Subtask #7
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 883 ms 96660 KB Output is correct
2 Correct 134 ms 29432 KB Output is correct
3 Runtime error 821 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #8
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 138 ms 29176 KB Output is correct
2 Correct 775 ms 80200 KB Output is correct
3 Correct 632 ms 51836 KB Output is correct

Subtask #9
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 735 ms 84012 KB Output is correct
2 Correct 729 ms 79864 KB Output is correct

Subtask #10
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 737 ms 80060 KB Output is correct
2 Correct 634 ms 51804 KB Output is correct