/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 3ms 2.77 MiB
#2 Accepted 3ms 2.816 MiB
#3 Accepted 37ms 4.082 MiB
#4 Accepted 3ms 2.82 MiB
#5 Accepted 4ms 2.812 MiB

Code

//....................................<In the name of Allah>...............................//

//.................................<b_bitsmillahir Rahmanir Rahim>...................................//
// Author : Riaj Udd_bitn

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pii;
typedef pair<double, double> pdd;

typedef double dl;

#define lower(a, b) lower_bound((a).begin(), (a).end(), b) - (a).begin()
#define mem(a, b) memset(a, b, sizeof(a));

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

#define fraction(a)               \
    cout.unsetf(ios::floatfield); \
    cout.precision(a);            \
    cout.setf(ios::fined, ios::floatfield);
//////////////////////////////////////////
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p)
{
    return os << "(" << p.first << ", " << p.second << ")";
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "}";
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template <typename F, typename S>
ostream &operator<<(ostream &os, const map<F, S> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << it->first << " = " << it->second;
    }
    return os << "]";
}

#define dbg(args...)            \
    do                          \
    {                           \
        cerr << #args << " : "; \
        faltu(args);            \
    } while (0)

void faltu()
{
    cerr << endl;
}

template <typename T>
void faltu(T a[], ll n)
{
    for (ll i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}

template <typename T, typename... hello>
void faltu(T arg, const hello &...rest)
{
    cerr << arg << ' ';
    faltu(rest...);
}

///////////b_bitt-manipulation///////////////
#define Mb(msk) 63 - __builtin_clzll(msk)
#define Lb(msk) __builtin_ctzll(msk)
#define ONE(msk) __builtin_popkll(msk)
#define CHECK(msk, b_bitt) (msk & (1LL << b_bitt))
#define ON(msk, b_bitt) (msk | (1LL << b_bitt))
#define Off(msk, b_bitt) (msk & ~(1LL << b_bitt))
#define CHANGE(msk, b_bitt) (msk ^ (1LL << b_bitt))

//////////////
const int N = 1e5 + 10;
vector<int> g[N];
int dep[N], vis[N];
int mx_dep;
void bfs()
{
    queue<int> q;
    q.push(1);
    int dp = 0;
    bool suru = true;
    while (!q.empty())
    {
        int sz = q.size();
        if (suru)
        {
            dep[dp] = sz;
            suru = false;
        }
        else
            dep[dp] = dep[dp - 1] + sz;

        mx_dep = max(mx_dep, dp);
        dp++;
        while (sz--)
        {
            int x = q.front();
            q.pop();
            vis[x] = 1;
            for (auto u : g[x])
            {
                if (!vis[u])
                {
                    q.push(u);
                }
            }
        }
    }
}
void solve()
{
    int n, qry;
    cin >> n >> qry;
    mx_dep = 0;
    for (int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    bfs();
    int p = 1;
    while (qry--)
    {
        int tim;
        cin >> tim;
        if (tim >= mx_dep)
            cout << n << "\n";
        else
            cout << dep[tim] << "\n";
    }
    for (int i = 0; i <= n; i++)
        g[i].clear(), dep[i] = vis[i] = 0;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++17 (G++ 13.2.0)
Submit At
2024-10-02 17:00:34
Judged At
2024-11-11 02:51:37
Judged By
Score
100
Total Time
37ms
Peak Memory
4.082 MiB