QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#848376 | #9996. 辞甲猾扎 | QOJQOJQOJ | WA | 629ms | 72224kb | C++14 | 4.2kb | 2025-01-08 20:04:44 | 2025-01-08 20:04:45 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
static const int MAXN = 1000000;
vector<int> adj[MAXN + 1];
int distB[MAXN + 1]; // 距离最近黑点的距离
bool isBlack[MAXN + 1]; // 标记是否初始黑色
bool visited[MAXN + 1]; // 用于最终判定是否被“白覆盖”或是黑点
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
// 读入黑色点
vector<int> blackNodes(k);
for(int i = 0; i < k; i++){
cin >> blackNodes[i];
}
// 建树
for(int i = 1; i <= n; i++){
adj[i].clear();
distB[i] = -1;
isBlack[i] = false;
visited[i] = false;
}
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// 1) 多源 BFS 计算每个点到最近黑点的距离 distB
queue<int>q;
for(int b : blackNodes){
isBlack[b] = true;
distB[b] = 0;
visited[b] = true; // 黑点本身可视为已经“无须再覆盖”
q.push(b);
}
while(!q.empty()){
int u = q.front();
q.pop();
for(int v : adj[u]){
if(distB[v] == -1){ // 尚未设置过
distB[v] = distB[u] + 1;
q.push(v);
}
}
}
// 2) 建立所有点 (或仅非黑点) 的列表,按 distB 从大到小排序
vector<int> nodes(n);
iota(nodes.begin(), nodes.end(), 1);
sort(nodes.begin(), nodes.end(), [&](int a, int b){
return distB[a] > distB[b];
});
// 预先为了后面找“到黑点的路径”,我们需要一个 BFS parent,
// 便于从节点往黑点方向走。这里可以在多源BFS时,记录 parent。
// 但也可以再次用 distB 的性质 + 邻居判断来“往距离更小的邻居”走。
// 为简单,我们重新记 parent。
vector<int> parent(n+1, -1);
// 再跑一遍多源 BFS,顺便记录 parent
{
for(int i=1; i<=n; i++){
parent[i] = -1;
}
queue<int>qq;
for(int b : blackNodes){
qq.push(b);
parent[b] = b; // 自己指向自己,作为根标记
}
while(!qq.empty()){
int u = qq.front(); qq.pop();
for(int v : adj[u]){
if(parent[v] == -1){
// 只要 distB[v] = distB[u]+1 即可确定 parent(v)=u
if(distB[v] == distB[u] + 1){
parent[v] = u;
qq.push(v);
}
}
}
}
}
// 3) 从距离大的节点开始遍历,若未被覆盖,则在它到某个黑点的中点处染白
int answer = 0;
for(int u : nodes){
// 黑点 (visited[u]==true) 已不需要处理;或者已被白覆盖也跳过
if(visited[u]) continue;
// distB[u] <= 0 代表它要么本身是黑点,要么与黑点重合
// 但如果能进来这里说明它不是黑点且 visited[u]=false,仅可能是 n=1 之类的边界
if(distB[u] <= 0) {
// distB[u] == 0 且非黑点 => 不存在这情况(因为0的都被标记visited=true)
// distB[u] < 0 => 如果无效(无黑点?), 题目给k>=1,一般不考虑
continue;
}
// 寻找“走 distB[u]/2 步”后的位置 M
int steps = distB[u] / 2;
int cur = u;
while(steps > 0){
cur = parent[cur];
steps--;
}
int M = cur; // 这里放一个白点
answer++;
// 从 M 出发,在半径 = distB[u] 范围内标记 visited = true
queue<pair<int,int>> coverQ;
coverQ.push({M, 0});
visited[M] = true;
while(!coverQ.empty()){
auto [x, distx] = coverQ.front();
coverQ.pop();
for(int y : adj[x]){
if(!visited[y] && distx + 1 <= distB[u]){
visited[y] = true;
coverQ.push({y, distx + 1});
}
}
}
}
cout << answer << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 629ms
memory: 72224kb
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:
124568
result:
wrong answer 1st lines differ - expected: '497', found: '124568'