fork download 
  1. #include<bits/stdc++.h>
  2. #include<ext/pb_ds/assoc_container.hpp>
  3. #include<ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. template<typename T>
  8. using ordered_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
  9.  
  10. #define ll long long
  11. #define ull unsigned long long
  12. #define pi pair<ll,ll>
  13. #define pii pair<ll,pi>
  14. #define inf 1000000000000000000
  15. #define iinf -1000000000000000000
  16. #define __   ios_base::sync_with_stdio(0);cin.tie();cout.tie();
  17. #define MOD 1000000007
  18. #define uu first
  19. #define vv second
  20. #define endl '\n'
  21.  
  22. pi operator+(pi a, ll x)     {return {a.uu + x, a.vv + x} ;}
  23. pi operator- (pi a, ll x)     {return {a.uu - x, a.vv - x} ;}
  24. pi operator* (pi a, ll x)     {return {a.uu * x, a.vv * x} ;}
  25. pi operator+(pi x, pi y) { return {x.uu + y.uu,x.vv + y.vv} ;}
  26. pi operator-(pi x,pi y) { return {x.uu - y.uu, x.vv - y.vv} ;}
  27. pi operator*(pi x,pi y) { return {x.uu * y.uu , x.vv * y.vv} ;}
  28. pi operator%(pi x,pi y) { return {x.uu % y.uu, x.vv % y.vv} ;}
  29.  
  30. const pi base = {103,101};
  31.  
  32. const pi  mod = {1000000021, 1e9 + 9 };
  33.  
  34. ll Set(ll N,ll pos){ return N=N | (1LL<<pos); }
  35. ll reset(ll N,ll pos){ return N= N & ~(1LL<<pos); }
  36. bool check(ll N,ll pos){ return (bool)(N & (1LL<<pos)); }
  37.  
  38. ll ar[]={0,0,1,-1};
  39. ll br[]={1,-1,0,0};
  40.  
  41. ///*******GEOMETRY**********///
  42. double PI=acos(-1.0);
  43.  
  44. double gcd(double a,double b){
  45.     return fabs(b)<1e-4?a:gcd(b,fmod(a,b));
  46. }
  47.  
  48. ///*******GEOMETRY**********///
  49.  
  50. ll sqrt_ (int64_t x) {
  51.     int64_t y = sqrt(x);
  52.     while (y * y > x) {
  53.       --y;
  54.     }
  55.     while (y * y <= x) {
  56.       ++y;
  57.     }
  58.     return y - 1;
  59. }
  60.  
  61. ll bigmod(ll n,ll pow){
  62. if(pow==0) return 1;
  63. if(pow==1) return n%MOD;
  64.  
  65. ll ans=bigmod(n,pow/2);
  66. ans=(ans*ans)%MOD;
  67.  
  68. if(pow%2==1){ans=(ans*n)%MOD;}
  69. return ans%MOD;
  70. }
  71.  
  72. ll fact[1000005];
  73.  
  74.  
  75. ll nCr(ll n,ll r){
  76.  
  77. ll ans=fact[n];
  78. ans=(ans*bigmod(fact[r],MOD-2))%MOD;
  79. ans=(ans*bigmod(fact[n-r],MOD-2))%MOD;
  80. return ans;
  81. }
  82.  
  83. string s,s1,s2;
  84. ll n,m;
  85. ll arr[5000010];
  86. ll brr[5000010];
  87. vector<ll>v,v1;
  88.  
  89. map<ll,ll>mp;
  90. ll vis[5000005];
  91. const ll N = 40005;
  92. vector<ll>gg[N];
  93. ll match[N], dist[N];
  94. ll idx;
  95. bool bfs(){
  96.     queue<ll>q;
  97.     for(ll i=1;i<=idx;i++){
  98.         if(match[i]==0){
  99.             dist[i]=0;
  100.             q.push(i);
  101.         }
  102.         else dist[i]=inf;
  103.     }
  104.     dist[0]=inf;
  105.  
  106.     while(!q.empty()){
  107.         ll u=q.front();
  108.         q.pop();
  109.         if(u!=0){
  110.             for(auto v:gg[u]){
  111.                 if(dist[match[v]]==inf){
  112.                     dist[match[v]]=dist[u]+1;
  113.                     q.push(match[v]);
  114.                 }
  115.             }
  116.         }
  117.     }
  118.     return (dist[0] != inf);
  119. }
  120.  
  121. bool dfs(ll u){
  122.     if(u!=0){
  123.         for(auto v:gg[u]){
  124.             if(dist[match[v]]==dist[u]+1){
  125.                 if(dfs(match[v])){
  126.                     match[v]=u;
  127.                     match[u]=v;
  128.                     return true;
  129.                 }
  130.             }
  131.         }
  132.         dist[u]=inf;
  133.         return false;
  134.     }
  135.     return true;
  136. }
  137.  
  138. ll max_match(){
  139.     ll matching =0;
  140.     while(bfs()){
  141.         for(ll i=1;i<=idx;i++){
  142.             if(match[i]==0&&dfs(i)) matching++;
  143.         }
  144.     }
  145.     return matching;
  146. }
  147.  
  148. // complexity: O(sqrt(V)*E).
  149.  
  150. int main()
  151. {__
  152.         ll i,j,a,b,c,d,e,f,g,x,y,z,t,k,l,r;
  153.         fact[0]=1;
  154.  
  155.       //  for(i=1;i<=1000000;i++) fact[i]=(fact[i-1]*i)%MOD;
  156.         ll ans=0,sum=0,temp;
  157.  
  158.  
  159. }
  160.  
  161.  
  162.  
  163.  
Success #stdin #stdout 0.01s 8636KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SRQ2kq
language:
C++14 (gcc 8.3)
created:
2 years 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!