QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#629712 | #4122. 嫁接树 | hhoppitree | 85 | 658ms | 15996kb | C++17 | 2.0kb | 2024-10-11 14:23:22 | 2024-10-11 14:23:22 |
Judging History
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'