Advertisement
Josif_tepe

Untitled

May 16th, 2023
615
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.13 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. typedef long long ll;
  5. const int INF = (1<<30);
  6. const ll inf = (1LL << 55LL);
  7. const int maxn = 300004;
  8. vector<int> graph[maxn];
  9. int arr[maxn];
  10. int parent[maxn];
  11. bool visited[maxn];
  12. //1000000000
  13. int n, S;
  14.  
  15. int tmpArr[maxn];
  16. int ret;
  17. void dfs(int node){
  18.     if(node == 0){
  19.         return;
  20.     }
  21.     int sosed;
  22.     for(int i =0 ; i <(int)graph[node].size(); i ++){
  23.         sosed = graph[node][i];
  24.         if(sosed != parent[node])continue;
  25.         if(tmpArr[node] > tmpArr[sosed]){
  26.             ret ++;
  27.             tmpArr[sosed] = tmpArr[node] ;
  28.             dfs(sosed);
  29.         }
  30.     }
  31. }
  32. int main()
  33. {
  34.     ios_base::sync_with_stdio(false);
  35.     cin >> n >> arr[0];
  36.     int a, b;
  37.     for(int i = 1; i <= n; i ++){
  38.         cin >> arr[i] >> b;
  39.         a = i;
  40.         parent[i] = b;
  41.         graph[a].push_back(b);
  42.         graph[b].push_back(a);
  43.     }
  44.     for(int j = 0; j <= n; j ++){
  45.             tmpArr[j] = arr[j];
  46.         }
  47.     for(int i = 1; i <= n; i ++){
  48.  
  49.         ret = 0;
  50.         S = i;
  51.         dfs(i);
  52.         cout << ret << "\n";
  53.     }
  54.     return 0;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement