/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 584.0 KiB
#2 Accepted 3ms 540.0 KiB
#3 Accepted 69ms 2.641 MiB
#4 Accepted 3ms 540.0 KiB
#5 Accepted 3ms 332.0 KiB

Code

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
// #define cerr cout
#include "algo/debug.h"
#else
#define deb(...) 30
#endif
#define ll long long
#define all(x) (x).begin(), (x).end()
#define f(i, n) for (int i = 0; i < n; i++)
const int N = 1e5 + 7;
#define int long long
vector<int> g[N];
bool vis[N];
int dis[N];
int n, qu;
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int tt;
    cin >> tt;
    while (tt--) {
        cin >> n >> qu;
        for (int i = 0; i < n + 5; i++)
            g[i].clear(), vis[i] = false, dis[i] = 0;
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            g[u].push_back(v);
            g[v].push_back(u);
        }
        map<int, int> level;
        queue<int> q;
        q.push(1);
        vis[1] = true;
        dis[1] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto v : g[u]) {
                if (!vis[v]) {
                    q.push(v);
                    dis[v] = dis[u] + 1;
                    vis[v] = true;
                }
            }
        }
        vector<int> v;
        for (int i = 1; i <= n; i++)
            v.push_back(dis[i]);
        sort(all(v));
        // for (auto a : v)
        //     cout << a << " ";
        // cout << qu << ' ';
        while (qu--) {  // 0 1 1 2 3
            int tf;
            cin >> tf;
            cout << upper_bound(all(v), tf) - v.begin() << '\n';
        }
        // cout << endl;
    }

    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:02:00
Judged At
2024-10-03 13:50:52
Judged By
Score
100
Total Time
69ms
Peak Memory
2.641 MiB