QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848386#9996. 辞甲猾扎QOJQOJQOJWA 601ms72332kbC++144.6kb2025-01-08 20:09:152025-01-08 20:09:16

Judging History

This is the latest submission verdict.

  • [2025-01-08 20:09:16]
  • Judged
  • Verdict: WA
  • Time: 601ms
  • Memory: 72332kb
  • [2025-01-08 20:09:15]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;

/*
  我们将按照上文所述:
   1) 先多源 BFS 得到 distB[u]: 每个点到最近黑点的距离
   2) 将非黑点按 distB[u] 降序排
   3) 依次扫描,若没被“覆盖”则把它选为白点,再在可覆盖范围内标覆盖
      (“覆盖”含义是,保证这批节点到此白点的距离 <= 它们到黑点的距离)
*/

static const int MAXN = 1000000;  // 题目 n <= 10^6

vector<int> adj[MAXN+1];
bool isBlack[MAXN+1];   // 标记某点是否初始黑
bool isCovered[MAXN+1]; // 标记某点是否已经被覆盖
int distB[MAXN+1];      // 到最近黑点的距离
int parentBFS[MAXN+1];  // BFS里记录某条最短路父亲(可选,若要还原路径)

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vector<int> blacks(k);
    for(int i=0; i<k; i++){
        cin >> blacks[i];
    }
    // 建图
    for(int i=1; i<=n; i++){
        adj[i].clear();
        isBlack[i] = false;
        isCovered[i] = false;
        distB[i] = INT_MAX;
        parentBFS[i] = -1;
    }
    for(int i=1; i<n; i++){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // 标记黑点
    for(int b: blacks){
        isBlack[b] = true;
    }

    // 1) 多源BFS, 初始化队列
    queue<int>q;
    for(int b: blacks){
        distB[b] = 0;
        q.push(b);
    }
    // BFS
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int w: adj[u]){
            if(distB[w] > distB[u] + 1){
                distB[w] = distB[u] + 1;
                q.push(w);
                parentBFS[w] = u;  // 可选
            }
        }
    }

    // 2) 收集所有非黑点,按 distB 降序 排
    vector<int> nodes;
    nodes.reserve(n);
    for(int i=1; i<=n; i++){
        if(!isBlack[i]){
            nodes.push_back(i);
        }
    }
    sort(nodes.begin(), nodes.end(), [&](int a,int b){
        return distB[a] > distB[b];
    });

    // 3) 依次扫描
    int answer = 0;
    // 我们需要一个辅助结构来做“可覆盖范围的标记”。
    // 实现手段之一:当我们决定在 x 染白,就从 x 出发做一个“小 BFS”,
    // 遍历那些与 x 的距离 step <= distB[x] 的节点,把它们标记 isCovered = true。
    // 且还要保证 step <= distB[y] (即 dist(x,y) <= distB[y])。
    // 这样就能正确覆盖不会变黑的区域。
    //
    // 为避免大规模重复 BFS,我们会设置一个 visited2[] 来标记本次小 BFS 的访问,
    // 并且每条边只会被访问一次或少几次,总体不会超过 O(n)~O(n log n)。
    //
    // 注:若写得更巧,还能合并到一次多源搜索里;此处为了展示思路,代码更直白一点。
    vector<bool> visited2(n+1,false);

    for(int x : nodes){
        if(!isCovered[x]){
            // x 尚未被覆盖,必须在 x 处放一个白点
            answer++;
            // 从 x 出发做受限 BFS
            // 限制条件:
            //   1) 距离步数 step <= distB[x]
            //   2) step <= distB[currentNode]
            // 这样才能保证“当前节点可被 x 覆盖”。
            fill(visited2.begin(), visited2.end(), false);
            queue<int>qq;
            qq.push(x);
            visited2[x] = true;
            isCovered[x] = true;

            int limit = distB[x]; // x 这个白点能覆盖到半径 limit
            int step = 0;         // BFS层数

            // 分层 BFS
            int layerSize = 1;
            int currentLayer = 0;
            while(!qq.empty()){
                int u = qq.front(); 
                qq.pop();
                layerSize--;

                for(int w: adj[u]){
                    if(!visited2[w]){
                        // 若 distB[w] >= distB[x] - (step+1),
                        // 等效于 step+1 <= distB[w] 且 step+1 <= distB[x]。
                        // 这里 step+1 <= limit 就是 step+1 <= distB[x]。
                        if(distB[w] >= step+1 && step+1 <= limit){
                            visited2[w] = true;
                            isCovered[w] = true;
                            qq.push(w);
                        }
                    }
                }

                if(layerSize==0){
                    step++;
                    layerSize = (int)qq.size();
                    if(step > limit) break;
                }
            }
        }
    }

    cout << answer << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 601ms
memory: 72332kb

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:

7423

result:

wrong answer 1st lines differ - expected: '497', found: '7423'