QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#848372#9996. 辞甲猾扎QOJQOJQOJWA 447ms60600kbC++141.8kb2025-01-08 20:03:252025-01-08 20:03:26

Judging History

This is the latest submission verdict.

  • [2025-01-08 20:03:26]
  • Judged
  • Verdict: WA
  • Time: 447ms
  • Memory: 60600kb
  • [2025-01-08 20:03:25]
  • Submitted

answer

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    
    vector<bool> isBlack(n+1, false);
    for(int i = 0; i < k; i++){
        int b;
        cin >> b;
        isBlack[b] = true;
    }
    
    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);
    }
    
    // Build set X: non-black vertices adjacent to at least one black vertex.
    vector<int> X;
    vector<bool> inX(n+1, false);
    for(int v = 1; v <= n; v++){
        if(isBlack[v]) continue;
        for(int nb : adj[v]){
            if(isBlack[nb]){
                if(!inX[v]){
                    inX[v] = true;
                    X.push_back(v);
                }
                break;
            }
        }
    }
    
    vector<bool> chosen(n+1, false);
    int countWhite = 0;
    
    // For each vertex in X, ensure that one of its neighbors is white.
    for(int u : X){
        bool found = false;
        for(int w : adj[u]){
            if(!isBlack[w] && chosen[w]){
                found = true;
                break;
            }
        }
        if(!found){
            int select = -1;
            for(int w : adj[u]){
                if(!isBlack[w]){
                    select = w;
                    break;
                }
            }
            // If no non-black neighbor found, select u itself.
            if(select == -1) select = u;
            if(!chosen[select]){
                chosen[select] = true;
                countWhite++;
            }
        }
    }
    
    cout << countWhite << "\n";
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 417ms
memory: 58732kb

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: 447ms
memory: 60600kb

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:

248264

result:

wrong answer 1st lines differ - expected: '216049', found: '248264'