fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define pb push_back
  7. #define pii pair<int, int>
  8. #define pll pair<ll, ll>
  9. #define vvi vector<vector<int>>
  10. #define vt vector
  11. #define arr array
  12. #define ALL(x) begin(x), end(x)
  13. #define rALL(x) rbegin(x), rend(x)
  14. #define SZ(x) x.size()
  15. #define P(x, y) make_pair(x, y)
  16. const int MOD1=998244353;
  17. const ll MOD2=1e9+7;
  18. const ll LINF=3e18;
  19. const int INF=1e9;
  20.  
  21. const int N=2e5;
  22. map<int, vector<int>> e;
  23. map<int, int> vis;
  24. vector<int> comp;
  25.  
  26. void dfs(int x){
  27.     vis[x] = 1;
  28.     comp.pb(x);
  29.     for (auto k : e[x]){
  30.     	if (vis[k]) continue;
  31.     	dfs(k);
  32.     }
  33. }
  34.  
  35. void solve(){
  36.     int n;
  37.     cin >> n;
  38.     for (int i = 0; i < n; i++){
  39.         int x, r;
  40.         cin >> x >> r;
  41.         e[x + r].pb(x - r);
  42.         e[x - r].pb(x + r);
  43.     }
  44.     int ans = 0;
  45.     for (auto [a, b] : e){
  46.     	if (vis[a]) continue;
  47.         dfs(a);
  48.  
  49.         int edge = 0;
  50.         for (auto x : comp) edge += (int)SZ(e[x]);
  51.  
  52.         ans += min(edge >> 1, (int)SZ(comp));
  53.         comp.clear();
  54.  
  55.         // the maximum bunnies for a connected component is the number of its nodes, the minimum bunnies is the number of its edges
  56.     }
  57.     cout << ans << '\n';
  58. }
  59.  
  60. int main(){
  61.     ios::sync_with_stdio(0);
  62.     cin.tie(0); cout.tie(0);
  63.  
  64.     solve();
  65.  
  66.     return 0;
  67. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
10
1000000000 1000000000
1000000000 1
-1000000000 1000000000
-1000000000 1
0 1
2 1
1 2
4 1
3 2
4 3
stdout
copy 
9
https://ideone.com/zoUfGt
language:
C++ (gcc 8.3)
created:
5 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!