/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 1.004 MiB
#2 Accepted 4ms 996.0 KiB
#3 Time Exceeded ≥1057ms ≥2.16 MiB
#4 Accepted 5ms 752.0 KiB
#5 Accepted 3ms 776.0 KiB

Code

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

const int MAX_N = 100005; // Maximum number of nodes in the tree

vector<int> adj[MAX_N]; // Adjacency list to represent the tree
int distances[MAX_N]; // To store distances of nodes from the root

void bfs(int root) {
    queue<int> q;
    q.push(root);
    memset(distances, -1, sizeof(distances));
    distances[root] = 0;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        for (int child : adj[node]) {
            if (distances[child] == -1) {
                distances[child] = distances[node] + 1;
                q.push(child);
            }
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N, Q;
        cin >> N >> Q;

        // Clearing the adjacency list for each test case
        for (int i = 1; i <= N; ++i) {
            adj[i].clear();
        }

        // Constructing the tree
        for (int i = 0; i < N - 1; ++i) {
            int U, V;
            cin >> U >> V;
            adj[U].push_back(V);
            adj[V].push_back(U);
        }

        bfs(1); // Start BFS from the root node (node 1)

        // Processing queries
        for (int i = 0; i < Q; ++i) {
            int X;
            cin >> X;
            int count = 0;
            for (int j = 1; j <= N; ++j) {
                if (distances[j] <= X) {
                    count++;
                }
            }
            cout << count << endl;
        }
    }
    return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-07 03:43:24
Judged At
2024-11-11 03:31:08
Judged By
Score
30
Total Time
≥1057ms
Peak Memory
≥2.16 MiB