QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848383#9996. 辞甲猾扎QOJQOJQOJWA 428ms67276kbC++144.1kb2025-01-08 20:05:442025-01-08 20:05:45

Judging History

This is the latest submission verdict.

  • [2025-01-08 20:05:45]
  • Judged
  • Verdict: WA
  • Time: 428ms
  • Memory: 67276kb
  • [2025-01-08 20:05:44]
  • Submitted

answer

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

// 全局常量、数据结构等
static const int MAXN = 1000000;  // n <= 1e6

vector<int> adj[MAXN + 1];  // 邻接表
bool isBlack[MAXN + 1];     // 标记是否是黑色
bool dominated[MAXN + 1];   // 标记是否已被白点支配
bool inWhiteSet[MAXN + 1];  // 标记是否在我们选的白集合中
int degGrey[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();
        isBlack[i] = false;
        dominated[i] = false;
        inWhiteSet[i] = false;
        degGrey[i] = 0;
    }

    for(int i = 0; i < n - 1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    // 标记黑点
    for(int b: blackNodes) {
        isBlack[b] = true;
    }

    // 建立“灰点”之间的森林:统计每个灰点在去掉黑点之后的度数
    // 如果一个节点是黑色,就相当于在灰色子图中被删除;它与其它灰节点的边也要在灰色子图里删除
    // 我们后续用一个队列做贪心,度数<=1的就可以进队列
    for(int u = 1; u <= n; u++){
        if(!isBlack[u]){ // u是灰色
            int countDegree = 0;
            for(int v: adj[u]){
                if(!isBlack[v]) countDegree++;
            }
            degGrey[u] = countDegree;
        }
    }

    // 将所有灰色节点中度数<=1的放入队列
    queue<int> Q;
    for(int u = 1; u <= n; u++){
        if(!isBlack[u] && degGrey[u] <= 1){
            Q.push(u);
        }
    }

    // 开始"叶子-父亲"的贪心:每次处理一个度数<=1的点(叶子)
    while(!Q.empty()){
        int leaf = Q.front();
        Q.pop();
        
        // 如果这个叶子还没被支配,则需要把它的邻居(如果存在)选为白点(或它自己若无邻居)
        if(!dominated[leaf]){
            // 查看是否还有邻居可以用来放白点
            // 可能整棵组件只剩自己 => 度数=0 => 必须自己放白
            bool hasParent = false;
            int parentNode = -1;

            // 在"灰色子图"里找到它的邻居
            for(int v: adj[leaf]){
                if(!isBlack[v]){
                    parentNode = v;
                    hasParent = true;
                    break;
                }
            }

            if(!hasParent){
                // 没邻居 => leaf是整组件唯一节点(或已删除到只剩它)
                // 只能把自己变成白色
                inWhiteSet[leaf] = true;
                dominated[leaf] = true;  // 同时它也支配自己
            } else {
                // 有邻居 => 把这个邻居选为白点
                int p = parentNode;
                if(!inWhiteSet[p]){
                    inWhiteSet[p] = true;
                }
                // 白点p会支配p自己和它所有灰色邻居
                // 标记它及相邻节点为 dominated
                dominated[p] = true;
                for(int w: adj[p]){
                    if(!isBlack[w]){ 
                        dominated[w] = true;
                    }
                }
            }
        }

        // 继续把leaf删除(灰色子图里)
        // 即把leaf从邻居们的degree里减去,然后若邻居变成新的叶子(度<=1),就入队
        for(int v: adj[leaf]){
            if(!isBlack[v]){
                degGrey[v]--;
                if(degGrey[v] == 1){
                    Q.push(v);
                }
            }
        }
        // 标记leaf自己在灰色子图中等价“删除”
        degGrey[leaf] = 0;
    }

    // 统计选中的白点数量
    int ans = 0;
    for(int i = 1; i <= n; i++){
        if(inWhiteSet[i]){
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 428ms
memory: 67276kb

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:

372290

result:

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