QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#848374 | #9996. 辞甲猾扎 | QOJQOJQOJ | WA | 604ms | 74336kb | C++14 | 8.4kb | 2025-01-08 20:04:15 | 2025-01-08 20:04:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
/*
We store:
- n, k
- blackNodes: list of initially black nodes
- edges: adjacency list for the tree
We perform:
1) Multi-source BFS from black nodes to get distBlack[u].
2) Sort non-black nodes by distBlack[u] descending.
3) Greedily place white nodes to "cover" them so they won't turn black.
*/
static const int MAXN = 1000000;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
// Read inputs
int n, k;
cin >> n >> k;
vector<int> black(k);
for(int i = 0; i < k; i++){
cin >> black[i];
black[i]--; // zero-based
}
// Edge adjacency
vector<vector<int>> adj(n);
for(int i = 0; i < n-1; i++){
int u,v;
cin >> u >> v;
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
// Special cases
if(k == n){
// All nodes are black already, no need to color anything white
cout << 0 << "\n";
return 0;
}
// If k == 0, no black nodes => final black is 0 => no need to color
// But problem states 1 <= k <= n, so k=0 does not occur.
// Step 1) Multi-source BFS from all black nodes
vector<int> distBlack(n, INT_MAX);
queue<int>q;
// Initialize the queue with black nodes
for(int b: black){
distBlack[b] = 0;
q.push(b);
}
// BFS
while(!q.empty()){
int u = q.front();
q.pop();
for(int nx : adj[u]){
if(distBlack[nx] > distBlack[u] + 1){
distBlack[nx] = distBlack[u] + 1;
q.push(nx);
}
}
}
// Step 2) We only care about nodes that are NOT black initially
// We'll sort them in descending order of distBlack[u].
// We also keep track if they're "covered" by an already placed white.
vector<int> nodes;
nodes.reserve(n - k);
vector<bool> isBlack(n, false);
for(int b: black) {
isBlack[b] = true;
}
for(int i = 0; i < n; i++){
if(!isBlack[i]) {
nodes.push_back(i);
}
}
sort(nodes.begin(), nodes.end(), [&](int a, int b){
return distBlack[a] > distBlack[b];
});
// We'll keep a "visited" or "covered" array
vector<bool> covered(n, false);
// For BFS parent tracking (to walk up the tree),
// we can store a BFS tree parent from the earlier multi-source BFS.
// We'll do another BFS (or we can store parents from the same BFS).
// For simplicity, we can store parents from the same BFS above.
vector<int> parent(n, -1);
// Re-run BFS for parent (or we do it once carefully)
// Let's do it carefully in the BFS above: we'll do a second BFS for that.
// Because the BFS above was multi-source, we can do a separate BFS for storing parents.
fill(parent.begin(), parent.end(), -1);
// We'll do the same multi-source BFS but store any valid parent
{
// reset
vector<int> dist2(n, INT_MAX);
queue<int> qq;
for(int b: black){
dist2[b] = 0;
qq.push(b);
parent[b] = b; // mark itself as root in BFS
}
while(!qq.empty()){
int u = qq.front(); qq.pop();
for(int nx: adj[u]){
if(dist2[nx] > dist2[u] + 1){
dist2[nx] = dist2[u] + 1;
parent[nx] = u;
qq.push(nx);
}
}
}
}
// Function to walk up "steps" times from node using parent[] chain
auto walkUp = [&](int start, int steps){
int cur = start;
while(steps > 0 && parent[cur] != cur){
cur = parent[cur];
steps--;
}
return cur;
};
// We'll keep adjacency again for a small BFS from each newly placed white node
// to mark coverage. But we want an efficient method, or we risk O(n^2).
// We'll do a small BFS up to radius = distBlack[u], but that might be large.
// Instead, we rely on the standard approach:
// When we place a white node "w" for a node "u" with distBlack[u] = d,
// it can cover all nodes v where dist(v, w) <= dBlack[u] - dist(v, u) ???
// Actually, simpler is the known approach:
// Place white node at "ancestor" = walkUp(u, distBlack[u]/2).
// Then skip a BFS-based coverage: we do a DS approach or we re-check coverage from that white node.
// However, the typical approach is: once we place a white node w, we do a BFS from w
// with radius = distBlack[u] (or something) and mark covered[] if possible.
//
// For correctness in large trees, we do a standard method:
// - We *mark covered for node u (and possibly an area around w).
// - But to do that effectively in O(n), we can store "lowest radius" from a white node
// or do a multi-source BFS from newly added whites, but that can be up to O(#white * n).
// A well-known trick: we process nodes from largest distBlack to smallest, so once we place
// a white node, we can greedily skip any node that is within the same "range".
// We'll implement a simpler BFS coverage approach with a queue, bounding the BFS by
// checking if "distBlack[v] >= distBlack[u] - dist(walkUpDist)", etc.
// We'll store an "active" queue approach to mark coverage in descending order.
// The final approach:
// For each node in descending order:
// if (covered[node]) continue
// d = distBlack[node]
// w = walkUp(node, d/2)
// placeWhiteCount++
// BFS from w, only proceed if distBlack[next] >= distBlack[u] - (distance from w so far)
// (this ensures we do not extend coverage beyond the ability to outpace black)
// Mark covered[] for all visited in that BFS.
int whiteNeeded = 0;
// We'll do an adjacency-based BFS for coverage each time we place a white node
// but in worst case could be large if we do it for many placed nodes.
// Typically the number of placed nodes won't exceed O(n/(something)), but let's try to be careful with complexity.
// We will implement it but be mindful to prune BFS quickly.
// We'll store a small local BFS function that starts from 'startNode' with "maxD = distBlack[u]"
// We'll also skip over any node that is already covered.
for (int u: nodes) {
if (covered[u]) continue; // already safe
int d = distBlack[u];
if (d == 0) {
// This means this node is black, but we don't process black nodes here anyway.
// or it is 0-dist from black => itself black. Just skip.
continue;
}
// place a new white at w
int stepsUp = d / 2; // integer division
int w = walkUp(u, stepsUp);
whiteNeeded++;
// BFS coverage
queue<int> Q;
Q.push(w);
covered[w] = true;
// We store distance from w in a local array or map to prune BFS
unordered_map<int,int> localDist;
localDist[w] = 0;
while(!Q.empty()){
int cur = Q.front(); Q.pop();
int cd = localDist[cur];
// We can move to neighbor if not covered, and
// if distBlack[neighbor] >= d - cd (meaning white arrives in time).
// Because from w to neighbor is cd+1 steps, so
// black distance needed to be at least (d - (cd+1)) for it to remain coverable.
for(int nx : adj[cur]){
if(!covered[nx]){
int cdNext = cd + 1;
// The condition: black wave arrives in distBlack[nx] steps, white wave in cdNext steps.
// We want cdNext <= distBlack[nx]. Actually, we want cdNext <= distBlack[nx]
// so that the wave of white is not strictly behind black.
// But even more precisely, we want cdNext <= d - (some margin) if we rely on "largest d so far".
// A simpler known condition: if cdNext <= distBlack[nx], we can mark it covered.
if(cdNext <= distBlack[nx]){
covered[nx] = true;
localDist[nx] = cdNext;
Q.push(nx);
}
}
}
}
}
cout << whiteNeeded << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 604ms
memory: 74336kb
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:
2279
result:
wrong answer 1st lines differ - expected: '497', found: '2279'