/ SeriousOJ /

Record Detail

Accepted


  
# Status Time Cost Memory Cost
#1 Accepted 2ms 3.527 MiB
#2 Accepted 3ms 3.277 MiB
#3 Accepted 44ms 6.285 MiB
#4 Accepted 3ms 3.238 MiB
#5 Accepted 2ms 3.277 MiB

Code

#include <bits/stdc++.h>
using namespace std;
#define SC               scanf
#define PF               printf
#define ull              unsigned long long
#define ld               long double
#define F                first
#define S                second
#define pb               push_back
#define sort_a(a)        sort(a.begin(),a.end());
#define sort_d(a)        sort(a.rbegin(),a.rend());
#define READ(f)          freopen(f, "r", stdin)
#define WRITE(f)         freopen(f, "w", stdout)
#define rev(s)           reverse(s.begin(),s.end())
#define P(ok)            cout << (ok ? "YES\n": "NO\n")
#define __Heart__              ios_base :: sync_with_stdio(false); cin.tie(NULL);
#define ll long long
typedef pair< ll , ll>                   PII;
const int sz = 1e5 + 5 ;
vector<int> Edge[sz] ;
int level[sz] ,  n , q , u , v , cnt = 0 , lev[sz] , mx = 0 , x;
bool vis[sz] ;
map < int , int > mp ;
void bfs(int id)
{
    queue<int>q;
    q.push(id) ;
    vis[id] = true;
    level[id]  = 0 ;
    while(!q.empty())
    {
        int parent = q.front() ;
        q.pop() ;
        for(int i = 0 ; i< Edge[parent].size() ; i++)
        {
            int child = Edge[parent][i] ;
            if(!vis[child])
            {
                vis[child] = true;
                level[child] = 1 + level[parent] ;
                mp[1 + level[parent]]++ ;
                mx = max(mx , 1 + level[parent]) ;
                q.push(child) ;
            }
        }

    }

}
void solve()
{
   cin >> n >> q ;
   for(int i = 0 ; i < n - 1; i++){
    cin >> u >> v ;
    Edge[u].pb(v) ;
    Edge[v].pb(u) ;
   }
   memset(level,0,sizeof level) ;
   memset(vis,false,sizeof vis) ;
   bfs(1);
   mp[0] = 0 ;
   for(int i = 1 ; i <= mx ; i++){
    mp[i] += mp[i - 1] ;
   }
   while(q--){
    cin >> x ;
    if(x >= mx) cout << mp[mx] + 1 << "\n" ;
    else cout << mp[x] + 1 << "\n" ;
   }
   mx = 0 ;
   mp.clear() ;
}
int main()
{
     __Heart__
     int t ; cin >> t ; while(t--) solve() ;
}

Information

Submit By
Type
Submission
Problem
P1053 Water on Tree
Language
C++20 (G++ 13.2.0)
Submit At
2024-05-03 22:06:04
Judged At
2024-05-05 21:10:04
Judged By
Score
100
Total Time
44ms
Peak Memory
6.285 MiB