/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 4ms 1.414 MiB
#2 Accepted 4ms 1.324 MiB
#3 Accepted 61ms 2.938 MiB
#4 Accepted 4ms 1.277 MiB
#5 Accepted 4ms 1.402 MiB

Code

/**
 *  written by Binoy Barman .
**/

#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
#define all(v) v.begin(), v.end()
#define Too_Many_Jobs int tts, tc = 1; cin >> tts; hell: while(tts--)
#define Dark_Lord_Binoy ios_base::sync_with_stdio(false); cin.tie(NULL);

#ifdef LOCAL
#include "unravel.hpp"
#else
#define dbg(...) 42
#endif
#define ll long long

const int N = 1e5 + 5;
int n, q, x, u, v;
vector<int> g[N];
bool vis[N];
int lvl[N], ans[N];

void bfs(int start) {
    memset(vis, 0, sizeof vis);
    memset(lvl, 0, sizeof lvl);
    memset(ans, 0, sizeof ans);
    queue<int> q;
    vis[start] = 1;
    lvl[start] = 0;
    ans[0]++;
    q.push(start);

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

        for (const auto& neighbor : g[current]) {
            if (!vis[neighbor]) {
                vis[neighbor] = 1;
                lvl[neighbor] = lvl[current] + 1;
                ans[lvl[neighbor]]++;
                q.push(neighbor);
            }
        }
    }
}

int32_t main() {
Dark_Lord_Binoy
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    Too_Many_Jobs {
        cin >> n >> q;
        for (int i = 1; i < n; i++) {
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        bfs(1);

        for (int i = 1; i < N; i++) {
            ans[i] += ans[i - 1];
        }
        while(q--) {
            cin >> x;
            cout << ans[x] << nl;
        }
        for (int i = 0; i <= n; i++) {
            g[i].clear();
        }
    }

    return 0;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Contest
Brain Booster #3
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-06 16:00:10
Judged At
2024-11-11 03:33:33
Judged By
Score
100
Total Time
61ms
Peak Memory
2.938 MiB