fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main(){
  5.     ios::sync_with_stdio(0);
  6.     cin.tie(0);
  7.  
  8.     int n, m;
  9.     cin >> n >> m;
  10.  
  11.     vector<vector<int>> adj(n + 1);
  12.     for(int i = 0; i < m; i++){
  13.         int u, v;
  14.         cin >> u >> v;
  15.         adj[u].push_back(v);
  16.         adj[v].push_back(u);
  17.     }
  18.  
  19.     int k;
  20.     cin >> k;
  21.  
  22.     vector<int> best(n + 1, -1);
  23.     priority_queue<pair<int,int>> pq;
  24.  
  25.     for(int i = 0; i < k; i++){
  26.         int p, r;
  27.         cin >> p >> r;
  28.         if(r > best[p]){
  29.             best[p] = r;
  30.             pq.push({r, p});
  31.         }
  32.     }
  33.  
  34.     while(!pq.empty()){
  35.         auto [power, u] = pq.top(); pq.pop();
  36.         if(power < best[u]) continue;
  37.         if(power == 0) continue;
  38.  
  39.         for(int v : adj[u]){
  40.             if(best[v] < power - 1){
  41.                 best[v] = power - 1;
  42.                 pq.push({power - 1, v});
  43.             }
  44.         }
  45.     }
  46.  
  47.     int ans = 0;
  48.     for(int i = 1; i <= n; i++){
  49.         if(best[i] >= 0) ans++;
  50.     }
  51.  
  52.     cout << ans << '\n';
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
4 3 1
1 2
1 3
2 4
2 1
stdout
copy 
3
https://ideone.com/Tkgan0
language:
C++14 (gcc 8.3)
created:
6 hours 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!