QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#848379 | #9996. 辞甲猾扎 | QOJQOJQOJ | WA | 868ms | 76256kb | C++14 | 5.6kb | 2025-01-08 20:05:10 | 2025-01-08 20:05:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
/*
We want the minimal set of initially-white vertices (chosen from the gray ones),
so that for every node v not originally black, distW(v) <= distB(v).
Steps:
1) Multi-source BFS from black nodes to get distB(v) for each v.
2) Sort "candidates" (the originally-gray nodes) in descending order of distB.
3) We'll keep a boolean array `dominated[v]` to track if we've already ensured
distW(v) <= distB(v).
4) Traverse from largest distB(...) to smaller. If node v is not dominated,
we pick a node X on the path from v to its nearest black node (roughly halfway)
and color X white. Then we do a BFS/mark so that all nodes u with
dist(u, X) <= distB(u) become dominated.
5) Count how many X's were picked. That is our answer.
We must be careful to implement the "mark dominated" step in O(...) time overall.
This is typically done by a BFS from X, but we must limit that BFS only to nodes
that satisfy distB(u) >= dist(u, X). That still can be done in an efficient manner
if we manage a queue carefully.
We'll verify correctness on the sample inputs.
*/
// Adjacency list
static const int MAXN = 1000000;
vector<int> adj[MAXN+1];
int distB[MAXN+1]; // distance to nearest black
bool isBlack[MAXN+1];
bool dominated[MAXN+1]; // have we already guaranteed distW(...) <= distB(...) ?
int parentInBFS[MAXN+1]; // to reconstruct BFS tree paths
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, k;
cin >> n >> k;
// Read which nodes are black
vector<int> blackNodes(k);
for(int i=0; i<k; i++){
cin >> blackNodes[i];
}
// Build adjacency
for(int i=1; i<=n; i++){
adj[i].clear();
isBlack[i] = false;
dominated[i] = false;
distB[i] = INT_MAX;
parentInBFS[i] = -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);
}
// Mark black
for(int b : blackNodes){
isBlack[b] = true;
}
// 1) Multi-source BFS from all black nodes
queue<int>q;
for(int b : blackNodes){
distB[b] = 0;
parentInBFS[b] = 0; // no parent
q.push(b);
}
while(!q.empty()){
int u = q.front();
q.pop();
for(int w : adj[u]){
// If we haven't visited w in BFS
if(distB[w] == INT_MAX){
distB[w] = distB[u] + 1;
parentInBFS[w] = u;
q.push(w);
}
}
}
// We'll gather the non-black nodes:
vector<int> candidates;
candidates.reserve(n - k);
for(int i=1; i<=n; i++){
if(!isBlack[i]){
candidates.push_back(i);
}
}
// 2) Sort in descending order of distB
sort(candidates.begin(), candidates.end(), [&](int a, int b){
return distB[a] > distB[b];
});
// We'll pick "initialWhite" to store which nodes we decide to paint white
vector<int> initialWhite;
initialWhite.reserve(n);
// BFS/queue usage for "mark dominated" in an overall O(n) manner:
// We'll define a small function that, once we pick X as white,
// we run a BFS from X, stopping if distB(u) < dist(u, X).
auto markDominated = [&](int start){
queue<int> Q;
// distance from X in this marking BFS
vector<int> distX;
distX.resize(0); // we'll not keep a big vector globally to save memory
distX.resize(n+1, INT_MAX);
distX[start] = 0;
dominated[start] = true;
Q.push(start);
while(!Q.empty()){
int u = Q.front();
Q.pop();
for(int w : adj[u]){
if(!dominated[w]){
// dist from X to w
int candidateDist = distX[u] + 1;
// We only can continue if candidateDist <= distB[w]
if(candidateDist <= distB[w]){
// then w is dominated
dominated[w] = true;
distX[w] = candidateDist;
Q.push(w);
}
}
}
}
};
// 3) Go in descending distB order. If a node is undominated, place white ~halfway up.
for(int v : candidates){
if(dominated[v]) continue;
if(distB[v] == INT_MAX){
// This node is completely disconnected from black?
// Then black can't reach it anyway, so it's safe automatically.
dominated[v] = true;
continue;
}
if(distB[v] == 0){
// Means it is black, but we excluded blacks from candidates.
// So we shouldn't get here. Just skip if some edge case.
continue;
}
// Move up the BFS-tree about distB[v]/2 steps:
// Because if distB[v] = d, then the path from v -> ... -> black-root
// has length d. We want the node X whose distance from v is (d+1)//2 (or floor(d/2), etc.).
int steps = (distB[v]+1)/2; // the 'middle' or 'ceiling half'
int x = v;
while(steps-- > 0 && parentInBFS[x] != -1){
x = parentInBFS[x];
}
// We'll pick `x` to be white:
initialWhite.push_back(x);
// Then mark all nodes that can now be dominated by x
markDominated(x);
}
// The answer is the size of initialWhite
cout << initialWhite.size() << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 868ms
memory: 76256kb
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:
2051
result:
wrong answer 1st lines differ - expected: '497', found: '2051'