fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int MAXN = 100005;
  8.  
  9. int N;
  10. vector<int> stars(MAXN);            // Stars of each city
  11. vector<vector<int>> adj(MAXN);       // Adjacency list for the tree
  12. int max_restaurants = 0;             // Store the maximum number of restaurants visited
  13.  
  14. // Depth-First Search to compute the longest increasing path
  15. void dfs(int node, int parent, int length) {
  16.     // Update the global max_restaurants count
  17.     max_restaurants = max(max_restaurants, length);
  18.  
  19.     // Explore all neighbors
  20.     for (int neighbor : adj[node]) {
  21.         if (neighbor == parent) continue;  // Skip the parent to avoid revisiting
  22.         // If the neighbor's stars are greater, we can eat there
  23.         if (stars[neighbor] > stars[node]) {
  24.             dfs(neighbor, node, length + 1);
  25.         } else {
  26.             // If not, we just move on without incrementing the dining count
  27.             dfs(neighbor, node, 1);
  28.         }
  29.     }
  30. }
  31.  
  32. int main() {
  33.     cin >> N;
  34.  
  35.     // Input the stars of each city
  36.     for (int i = 1; i <= N; i++) {
  37.         cin >> stars[i];
  38.     }
  39.  
  40.     // Input the roads (edges)
  41.     for (int i = 1; i < N; i++) {
  42.         int u, v;
  43.         cin >> u >> v;
  44.         adj[u].push_back(v);
  45.         adj[v].push_back(u);
  46.     }
  47.  
  48.     // Start DFS from every city to ensure we check all possible starting points
  49.     for (int i = 1; i <= N; i++) {
  50.         dfs(i, -1, 1);  // Start DFS from city i, no parent (-1), starting length is 1
  51.     }
  52.  
  53.     // Output the result
  54.     cout << max_restaurants << endl;
  55.  
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0.01s 5680KB
comments (?)
stdin
copy 
6
4 1 3 2 5 3
1 2
1 3
1 4
4 5
4 6
stdout
copy 
2
https://ideone.com/CJnqSV
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!