QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#629712#4122. 嫁接树hhoppitree85 658ms15996kbC++172.0kb2024-10-11 14:23:222024-10-11 14:23:22

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 14:23:22]
  • 评测
  • 测评结果:85
  • 用时:658ms
  • 内存:15996kb
  • [2024-10-11 14:23:22]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 5, C = 18;

int n, m, col[N];
double P, a[C + 5];
vector<int> G[N];
vector< pair<int, int> > E;
double f[N], g[N];
int wf[N];

void dfs(int x, int fa = -1) {
    double h[C + 5];
    for (int i = 1; i <= C; ++i) h[i] = a[i];
    if (col[x]) {
        for (int i = 1; i <= C; ++i) {
            if ((i == abs(col[x])) != (col[x] > 0)) h[i] = -1e9;
        }
    }
    for (auto v : G[x]) {
        if (v == fa) continue;
        dfs(v, x);
        for (int i = 1; i <= C; ++i) {
            h[i] += (i == wf[v] ? g : f)[v];
        }
    }
    wf[x] = max_element(h + 1, h + C + 1) - h;
    f[x] = h[wf[x]], g[x] = -1e9;
    for (int i = 1; i <= C; ++i) {
        if (i != wf[x]) g[x] = max(g[x], h[i]);
    }
}

int check(double res) {
    if (E.empty()) {
        dfs(1);
        return f[1] > res;
    }
    if (E.size() == 1) {
        for (int i = 1; i <= C; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (j == E[0].first) col[j] = i;
                else if (j == E[0].second) col[j] = -i;
                else col[j] = 0;
            }
            dfs(1);
            if (f[1] > res) return 1;
        }
        return 0;
    }
    dfs(1);
    return (f[1] > res);
}

signed main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i < n; ++i) {
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for (int i = 1, x, y; i <= m; ++i) {
        scanf("%d%d", &x, &y);
        E.push_back({x, y});
    }
    scanf("%lf", &P);
    double L = 0, R = n / (1 + P / n), res = 0;
    while (fabs(L - R) > 1e-5) {
        double mid = (L + R) / 2;
        for (int i = 1; i <= C; ++i) {
            a[i] = ((double)1 / i - mid * P * i);
        }
        if (check(mid)) {
            res = mid, L = mid;
        } else {
            R = mid;
        }
    }
    printf("%.3lf\n", res);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 242ms
memory: 15040kb

input:

80000 0
1 2
1 3
2 4
1 5
5 6
6 7
2 8
2 9
6 10
7 11
3 12
10 13
9 14
9 15
9 16
9 17
15 18
15 19
13 20
10 21
11 22
4 23
23 24
9 25
8 26
14 27
16 28
6 29
5 30
9 31
13 32
6 33
23 34
15 35
27 36
25 37
13 38
18 39
1 40
13 41
25 42
19 43
5 44
3 45
26 46
24 47
14 48
9 49
20 50
11 51
23 52
5 53
9 54
29 55
26 5...

output:

66022.383

result:

ok single line: '66022.383'

Test #2:

score: 5
Accepted
time: 249ms
memory: 14816kb

input:

84000 0
1 2
1 3
2 4
1 5
5 6
6 7
2 8
2 9
6 10
7 11
3 12
10 13
9 14
9 15
9 16
9 17
15 18
15 19
13 20
10 21
11 22
4 23
23 24
9 25
8 26
14 27
16 28
6 29
5 30
9 31
13 32
6 33
23 34
15 35
27 36
25 37
13 38
18 39
1 40
13 41
25 42
19 43
5 44
3 45
26 46
24 47
14 48
9 49
20 50
11 51
23 52
5 53
9 54
29 55
26 5...

output:

69617.050

result:

ok single line: '69617.050'

Test #3:

score: 5
Accepted
time: 270ms
memory: 15348kb

input:

88000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

73247.333

result:

ok single line: '73247.333'

Test #4:

score: 5
Accepted
time: 282ms
memory: 15544kb

input:

92000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

76902.517

result:

ok single line: '76902.517'

Test #5:

score: 5
Accepted
time: 303ms
memory: 15836kb

input:

100000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55...

output:

84305.667

result:

ok single line: '84305.667'

Test #6:

score: 5
Accepted
time: 275ms
memory: 15552kb

input:

90000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

0.606

result:

ok single line: '0.606'

Test #7:

score: 5
Accepted
time: 276ms
memory: 15540kb

input:

92000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

0.203

result:

ok single line: '0.203'

Test #8:

score: 5
Accepted
time: 297ms
memory: 15144kb

input:

95000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

0.068

result:

ok single line: '0.068'

Test #9:

score: 5
Accepted
time: 299ms
memory: 15724kb

input:

98000 0
1 2
1 3
1 4
4 5
5 6
2 7
6 8
3 9
3 10
9 11
9 12
7 13
1 14
7 15
1 16
3 17
15 18
8 19
19 20
15 21
3 22
19 23
18 24
15 25
18 26
15 27
4 28
10 29
22 30
16 31
13 32
15 33
4 34
16 35
19 36
21 37
21 38
19 39
12 40
10 41
5 42
23 43
14 44
22 45
1 46
4 47
25 48
9 49
25 50
13 51
23 52
15 53
14 54
12 55
...

output:

0.088

result:

ok single line: '0.088'

Test #10:

score: 5
Accepted
time: 306ms
memory: 15996kb

input:

100000 0
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
2...

output:

0.155

result:

ok single line: '0.155'

Test #11:

score: 0
Wrong Answer
time: 278ms
memory: 11588kb

input:

15000 1
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

12084.783

result:

wrong answer 1st lines differ - expected: '12084.733', found: '12084.783'

Test #12:

score: 5
Accepted
time: 36ms
memory: 12660kb

input:

16000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

12869.817

result:

ok single line: '12869.817'

Test #13:

score: 5
Accepted
time: 43ms
memory: 13092kb

input:

17000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

13659.067

result:

ok single line: '13659.067'

Test #14:

score: 5
Accepted
time: 387ms
memory: 11748kb

input:

18000 1
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

14445.067

result:

ok single line: '14445.067'

Test #15:

score: 0
Wrong Answer
time: 48ms
memory: 11452kb

input:

20000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

16042.050

result:

wrong answer 1st lines differ - expected: '16042.017', found: '16042.050'

Test #16:

score: 0
Wrong Answer
time: 435ms
memory: 11308kb

input:

16000 1
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

0.286

result:

wrong answer 1st lines differ - expected: '0.285', found: '0.286'

Test #17:

score: 5
Accepted
time: 39ms
memory: 11832kb

input:

17000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

0.143

result:

ok single line: '0.143'

Test #18:

score: 5
Accepted
time: 658ms
memory: 12940kb

input:

18000 1
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

0.071

result:

ok single line: '0.071'

Test #19:

score: 5
Accepted
time: 45ms
memory: 11448kb

input:

19000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

0.095

result:

ok single line: '0.095'

Test #20:

score: 5
Accepted
time: 48ms
memory: 11960kb

input:

20000 2
1 2
2 3
1 4
4 5
1 6
5 7
4 8
4 9
9 10
9 11
4 12
3 13
13 14
11 15
15 16
13 17
15 18
11 19
7 20
11 21
7 22
12 23
14 24
22 25
21 26
24 27
10 28
21 29
12 30
23 31
14 32
1 33
7 34
17 35
11 36
17 37
6 38
12 39
1 40
29 41
16 42
6 43
24 44
18 45
27 46
22 47
15 48
17 49
21 50
15 51
1 52
25 53
27 54
26...

output:

0.189

result:

ok single line: '0.189'