fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. #define hell                         1000000007
  4. #define lcm(a,b)                     (a*b)/__gcd(a,b)
  5. #define ll                           long long
  6. #define vll                          vector<ll>
  7. #define vi                           vector<int>
  8. #define pll                          vector< pair<ll,ll> >
  9. #define pb                           push_back
  10. #define mp                           make_pair
  11. #define all(v)                       v.begin(),v.end()
  12. #define lbnd                         lower_bound
  13. #define ubnd                         upper_bound
  14. #define bs                           binary_search
  15. #define F                            first
  16. #define S                            second
  17. #define rep(i,a,b)                   for(i=a;i<b;i++)
  18. #define parr(a,n)                    for(i=0;i<n;i++) cout<<a[i]<<" ";cout<<endl;
  19. #define pcont(a)                     for(auto i:a) cout<<i<<" ";cout<<endl;
  20. #define ret(x)                       return cout<<x,0;
  21. #define dbg(x)                       cerr << #x << " is " << x << endl;
  22. #define endl                           '\n'
  23.  
  24. using namespace std;
  25. vll adj[100001];
  26. bool vis[100001];
  27. ll dp[100001];
  28. stack<ll> st;
  29. ll calc(ll s)
  30. {
  31.     if(dp[s]!=-1)
  32.         return dp[s];
  33.     if(adj[s].size()==0)
  34.         return dp[s]=1;
  35.     ll inc=1,exc=0;
  36.     for(auto it:adj[s])
  37.     {
  38.         exc+=calc(it);
  39.     }
  40.     for(auto it:adj[s])
  41.     {
  42.         ll val=0;
  43.         for(auto jt:adj[it])
  44.         {
  45.             val+=calc(jt);
  46.         }
  47.         inc+=min(calc(it),val);
  48.     }
  49.     dp[s]=min(inc,exc);
  50.     return dp[s];
  51. }
  52. void dfs(ll i)
  53. {
  54.     vis[i]=true;
  55.     for(auto it:adj[i])
  56.     {
  57.         if(!vis[it])
  58.             dfs(it);
  59.     }
  60.     st.push(i);
  61. }
  62. int main()
  63. {
  64.     ios_base::sync_with_stdio(false);
  65.     cin.tie(NULL);cout.tie(NULL);
  66.  
  67.     ll i,j,n,t=1,k=0,cnt=0,mini=LLONG_MAX,maxi=LLONG_MIN,ans=0;
  68.     ll m;
  69.     cin>>n;
  70.     m=n-1;
  71.     rep(i,0,m)
  72.     {
  73.         cin>>j>>k;
  74.         adj[j].pb(k);
  75.     }
  76.     for(i=0;i<100001;i++)
  77.         dp[i]=-1;
  78.     memset(vis,false,sizeof(vis));
  79.     for(i=1;i<=n;i++)
  80.     {
  81.         if(!vis[i])
  82.             dfs(i);
  83.     }
  84.     ans=calc(st.top());
  85.     cout<<ans;
  86.     return 0;
  87. }
  88.  
Success #stdin #stdout 0s 6264KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/iwWkF5
problem PT07X, based on SPOJ submission 22070700 (CPP14), 2018-07-30 19:19:59
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!