/ SeriousOJ /

Record Detail

Time Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 328.0 KiB
#2 Accepted 3ms 512.0 KiB
#3 Time Exceeded ≥1049ms ≥2.0 MiB
#4 Accepted 1ms 540.0 KiB
#5 Accepted 2ms 540.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
#define vi vector<int>
//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, vector<vi>& adj, vi& distances) {
    queue<int> q;
    q.push(root);
    //memset(distances, -1, sizeof(distances));


    distances[root] = 0;
    int vis[distances.size()] = {0}; vis[root] = 1;
    while (!q.empty()) {
        int node = q.front();
        q.pop();

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

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


        vector<vi> adj(N+1);
        vi dis(N+1, -1);
        // 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, adj, dis); // 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 (dis[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:42:34
Judged At
2024-11-11 03:31:10
Judged By
Score
30
Total Time
≥1049ms
Peak Memory
≥2.0 MiB