QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#370865 | #791. Mousetrap | Camillus | 0 | 162ms | 66068kb | C++20 | 1.1kb | 2024-03-29 18:05:17 | 2024-03-29 18:05:18 |
Judging History
answer
/// @author Camillus <3
#include "bits/stdc++.h"
using namespace std;
static constexpr int max_n = 2'000'000;
vector<int> g[max_n];
int parent[max_n];
int root;
int dp[max_n];
void dfs(int u, int p, int sum) {
parent[u] = -1;
auto it = find(g[u].begin(), g[u].end(), p);
if (it != g[u].end()) g[u].erase(it);
for (int v : g[u]) {
dfs(v, u, sum + g[v].size() - 2);
}
if (g[u].empty()) {
dp[u] = sum;
} else {
if (g[u].size() == 1) {
dp[u] = sum;
} else {
sort(g[u].begin(), g[u].end(), [&](int u, int v) -> bool {
return dp[u] > dp[v];
});
dp[u] = dp[1] + 1;
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> root >> m;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(root, -1, 1);
cout << dp[m] << '\n';
return 0;
}
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 20
Accepted
time: 0ms
memory: 3560kb
input:
10 2 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
10 1 10 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5
output:
3
result:
ok single line: '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
10 1 10 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3708kb
input:
9 1 7 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 3ms
memory: 3576kb
input:
10 1 10 1 2 3 2 4 3 5 3 6 4 7 3 8 7 9 2 10 5
output:
3
result:
ok single line: '3'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3668kb
input:
8 1 8 1 2 3 2 4 3 5 4 6 2 7 6 8 3
output:
2
result:
ok single line: '2'
Test #7:
score: -20
Wrong Answer
time: 2ms
memory: 3620kb
input:
10 3 2 3 1 1 2 2 4 2 5 2 6 7 5 8 5 9 6 10 6
output:
1
result:
wrong answer 1st lines differ - expected: '5', found: '1'
Subtask #2:
score: 0
Wrong Answer
Test #11:
score: 0
Wrong Answer
time: 162ms
memory: 66068kb
input:
1000000 1 2 2 1 3 2 4 2 5 3 6 3 7 4 8 4 9 5 10 5 11 6 12 6 13 7 14 7 15 8 16 8 17 9 18 9 19 10 20 10 21 11 22 11 23 12 24 12 25 13 26 13 27 14 28 14 29 15 30 15 31 16 32 16 33 17 34 17 35 18 36 18 37 19 38 19 39 20 40 20 41 21 42 21 43 22 44 22 45 23 46 23 47 24 48 24 49 25 50 25 51 26 52 26 53 27 5...
output:
1
result:
wrong answer 1st lines differ - expected: '36', found: '1'
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%