fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAXN = 3e5+7;
  5. int n;
  6.  
  7. vector<int> graf[MAXN];
  8.  
  9. int akt_spr; //Przekazuję z maina którą wartość aktualnie sprawdzam
  10.  
  11. bool sprawdz(int poprz, int v, int ile) {
  12. 	//Potrzebuję graf[v].size()-1 ekip budowlanych ale w każdej jednostce czasowej dostaję akt_spr
  13. 	//i jeszcze może coś w ile zostało do wykorzystania
  14.     ile += akt_spr - (graf[v].size() - 1);
  15.     if(v==1) ile--; //Bo korzeń nie ma ojca dlatego powinnam była tam wyżej zrobić zamiast
  16.     //- (graf[v].size()-1) po prostu - graf[v].size()
  17.     if(ile<0) return 0; //No i tutaj jak mi wychodzi ujemnie to się nie da
  18.  
  19.     for(auto sasiad : graf[v]) {
  20.         if(sasiad != poprz) {
  21.             bool akt = sprawdz(v, sasiad, ile);
  22.             if(!akt) return 0;
  23.         }
  24.     }
  25.     return 1;
  26. }
  27.  
  28. int main() {
  29.  
  30.     cin >> n;
  31.  
  32.     for(int i=0; i<n-1; i++) {
  33.         int a, b;
  34.         cin >> a >> b;
  35.         graf[a].push_back(b);
  36.         graf[b].push_back(a);
  37.     }
  38.  
  39. 	//Pomińmy fakt że działa to w O(n^2), bo dostaję WA i tak
  40.  
  41.     for(int i=0; i<=n; i++) {
  42.         akt_spr = i;
  43.         if(sprawdz(0, 1, 0)) {
  44.             cout << i << "\n";
  45.             return 0;
  46.         }
  47.     }
  48.  
  49.  
  50.     return 0;
  51. }
Success #stdin #stdout 0.01s 10568KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ax7JxF
language:
C++ (gcc 8.3)
created:
4 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!