fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long int
  4.  
  5. // 9th Aug 2025 Zomato
  6.  
  7. int main()
  8. {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(NULL);
  11.     int n, e;
  12.     cin >> n >> e;
  13.     vector<int> adj[n + 1];
  14.     vector<int> stone(n + 1);
  15.     priority_queue<pair<int, int>> pq;
  16.     for (int i = 1; i <= n; i++)
  17.     {
  18.         cin >> stone[i];
  19.         pq.push({stone[i], i});
  20.     }
  21.     for (int i = 0; i < e; i++)
  22.     {
  23.         int u, v;
  24.         cin >> u >> v;
  25.         adj[u].push_back(v);
  26.         adj[v].push_back(u);
  27.     }
  28.     vector<int> vis(n + 1, 0);
  29.     int ans = 0;
  30.     while (!pq.empty())
  31.     {
  32.         auto it = pq.top();
  33.         pq.pop();
  34.         int val = it.first;
  35.         int nd = it.second;
  36.         if (vis[nd] == 1)
  37.             continue;
  38.         vis[nd] = 1;
  39.         for (auto tt : adj[nd])
  40.         {
  41.             if (val - (stone[tt]) > 1)
  42.             {
  43.                 ans += (val - 1) - stone[tt];
  44.                 stone[tt] = val - 1;
  45.                 pq.push({val - 1, tt});
  46.             }
  47.         }
  48.     }
  49.  
  50.     cout << ans << endl;
  51.  
  52.     return 0;
  53. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
5 4
1 5 7 8 3
1 2
2 3
2 4
3 5
stdout
copy 
10
https://ideone.com/LUHBVP
language:
C++14 (gcc 8.3)
created:
4 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!