/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 1ms 540.0 KiB

Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int maxNodesVisited(int N, int K, vector<vector<int>>& edges) {
    vector<vector<int>> adj(N + 1);  // Adjacency list for the tree
    vector<int> dist(N + 1, -1);     // Distance from node 1
    
    // Build the adjacency list
    for (auto& edge : edges) {
        int u = edge[0], v = edge[1];
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // BFS to calculate distances from node 1
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        for (int neighbor : adj[node]) {
            if (dist[neighbor] == -1) {  // Not visited
                dist[neighbor] = dist[node] + 1;
                q.push(neighbor);
            }
        }
    }
    
    // Sort nodes by distance in descending order
    vector<int> nodes(N);
    for (int i = 1; i <= N; ++i) {
        nodes[i - 1] = i;
    }
    
    sort(nodes.begin(), nodes.end(), [&](int a, int b) {
        return dist[a] > dist[b];
    });
    
    // Calculate the maximum number of nodes Thakur can visit
    int totalVisits = 0;
    int revisits = 0;
    
    for (int node : nodes) {
        if (dist[node] <= revisits && revisits < K) {
            ++revisits;
            ++totalVisits;
        } else if (dist[node] <= revisits) {
            ++totalVisits;
        }
    }
    
    return totalVisits;
}

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<vector<int>> edges(N - 1, vector<int>(2));
    for (int i = 0; i < N - 1; ++i) {
        cin >> edges[i][0] >> edges[i][1];
    }
    
    cout << maxNodesVisited(N, K, edges) << endl;
    
    return 0;
}

Information

Submit By
Type
Pretest
Problem
P1111 Thakurs tree game
Language
C++17 (G++ 13.2.0)
Submit At
2024-11-05 16:05:31
Judged At
2024-11-05 16:05:31
Judged By
Score
0
Total Time
1ms
Peak Memory
540.0 KiB