QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #334561 | #1368. Kth Subtree | steventan | WA | 1ms | 7988kb | C++14 | 1.4kb | 2024-02-22 05:00:38 | 2024-02-22 05:00:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5005;
vector<int> tree[MAXN];
int sizes[MAXN];
long long dp[MAXN][MAXN] = {{0}};
int n;
long long K;
void dfs(int cur, int prev) {
sizes[cur] = 1;
dp[cur][1] = 1;
for (int nei : tree[cur]) {
if (nei != prev) {
dfs(nei, cur);
vector<int> temp(n + 1, 0);
for (int i = 1; i <= sizes[cur]; i++) {
for (int j = 1; i + j <= n; j++) {
temp[i + j] += dp[cur][i] * dp[nei][j];
}
}
for (int i = 0; i <= n; i++) {
dp[cur][i] += temp[i];
}
sizes[cur] += sizes[nei];
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> K;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
u--; v--;
tree[u].push_back(v);
tree[v].push_back(u);
}
dfs(0, -1);
long long count[n + 1];
long long psum = 0;
int res = -1;
for (int i = 1; i <= n; i++) {
count[i] = 0;
for (int j = 0; j < n; j++) {
count[i] += dp[j][i];
}
psum += count[i];
if (psum >= K) {
res = i;
break;
}
}
cout << res << endl;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 7988kb
input:
100 116588 43 57 39 96 22 83 42 93 45 34 43 78 38 40 3 73 63 100 57 13 96 41 64 6 19 91 98 81 91 45 100 38 12 50 19 82 43 56 63 93 75 34 62 76 60 46 18 79 11 55 16 7 59 69 38 4 23 60 45 54 11 3 43 87 85 69 83 16 16 53 85 32 45 52 57 88 2 63 53 92 51 27 29 37 41 62 73 90 62 100 43 90 13 50 56 23 91 5...
output:
11
result:
ok single line: '11'
Test #2:
score: 0
Accepted
time: 1ms
memory: 6052kb
input:
100 116589 43 57 39 96 22 83 42 93 45 34 43 78 38 40 3 73 63 100 57 13 96 41 64 6 19 91 98 81 91 45 100 38 12 50 19 82 43 56 63 93 75 34 62 76 60 46 18 79 11 55 16 7 59 69 38 4 23 60 45 54 11 3 43 87 85 69 83 16 16 53 85 32 45 52 57 88 2 63 53 92 51 27 29 37 41 62 73 90 62 100 43 90 13 50 56 23 91 5...
output:
12
result:
ok single line: '12'
Test #3:
score: -100
Wrong Answer
time: 1ms
memory: 7948kb
input:
100 117057262442603580 43 57 39 96 22 83 42 93 45 34 43 78 38 40 3 73 63 100 57 13 96 41 64 6 19 91 98 81 91 45 100 38 12 50 19 82 43 56 63 93 75 34 62 76 60 46 18 79 11 55 16 7 59 69 38 4 23 60 45 54 11 3 43 87 85 69 83 16 16 53 85 32 45 52 57 88 2 63 53 92 51 27 29 37 41 62 73 90 62 100 43 90 13 5...
output:
-1
result:
wrong answer 1st lines differ - expected: '97', found: '-1'