QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#848369 | #9996. 辞甲猾扎 | QOJQOJQOJ | WA | 379ms | 67976kb | C++14 | 1.8kb | 2025-01-08 20:03:00 | 2025-01-08 20:03:01 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; long long k;
cin >> n >> k;
vector<int> blackSeeds;
blackSeeds.resize(0);
vector<int> isBlack(n+1,0);
// 读取初始黑点
for(int i = 0; i < k; i++){
int x;
cin >> x;
isBlack[x] = 1;
blackSeeds.push_back(x);
}
// 构建树的邻接表
vector<vector<int>> adj(n+1);
for(int i = 0; i < n-1; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 多源 BFS 计算距离
vector<int> dist(n+1, -1);
deque<int> dq;
for(int b : blackSeeds){
dist[b] = 0;
dq.push_back(b);
}
while(!dq.empty()){
int u = dq.front();
dq.pop_front();
for(int nei : adj[u]){
if(dist[nei] == -1){
dist[nei] = dist[u] + 1;
dq.push_back(nei);
}
}
}
// 统计最大距离并构造频率数组
int maxd = 0;
for(int i = 1; i <= n; i++){
if(dist[i] > maxd) maxd = dist[i];
}
vector<int> freq(maxd+2, 0);
for(int i = 1; i <= n; i++){
if(dist[i] >= 0 && dist[i] <= maxd)
freq[dist[i]]++;
}
// 找到第 k 个点的距离 d_k
long long cum = 0;
int d_k = 0;
for(int d = 0; d <= maxd; d++){
cum += freq[d];
if(cum >= k){
d_k = d;
break;
}
}
// 答案是距离恰好为 d_k+1 的点的数量
int target = d_k + 1;
long long ans = 0;
if(target <= maxd)
ans = freq[target];
else
ans = 0;
cout << ans << "\n";
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 377ms
memory: 66328kb
input:
1000000 250 4246 6001 15765 16292 18291 18607 20931 24218 25916 28742 34837 37283 38797 38805 45707 47625 47981 55382 60377 60815 61528 71455 73316 79270 81165 88222 93488 95638 99798 100415 100686 107252 107624 110367 116459 118365 121070 130962 131316 132856 141146 152992 153050 154652 156855 1669...
output:
497
result:
ok single line: '497'
Test #2:
score: -100
Wrong Answer
time: 379ms
memory: 67976kb
input:
1000000 200000 9 11 14 17 27 43 45 51 54 56 65 68 69 79 80 81 83 100 104 111 112 113 118 119 121 122 126 140 141 142 144 148 152 156 159 160 161 175 180 181 187 188 189 194 196 208 219 237 242 243 245 247 250 254 255 272 286 291 297 302 307 310 312 316 317 324 325 326 327 330 334 340 350 357 358 361...
output:
273886
result:
wrong answer 1st lines differ - expected: '216049', found: '273886'