fork download
copy 
  1. #include <bits/stdc++.h>
  2. // #pragma optimize ("g",on)
  3. // #pragma GCC optimize ("inline")
  4. // #pragma GCC optimize ("Ofast")
  5. // #pragma GCC optimize ("unroll-loops")
  6. // #pragma GCC optimize ("03")
  7. // #pragma comment(linker, "/stack:200000000")
  8. // #pragma warning(disable : 4996)
  9. using namespace std;
  10. const int N=1e5+5;
  11. #define all(x) (x).begin(), (x).end()
  12. #define bll(x) (x), (x)+n
  13. #define forn(i, n) for(int i=0; i < (n); ++i)
  14. #define forauto(i, n) for(int (i):(n));
  15. #define scanfor(a, n) for(int i=0;i <(n); ++i)scanf("%lld",a+i)
  16. #define int long long
  17. #define pb push_back
  18. #define NO {cout<<"NO\n";return;}
  19. #define YES {cout<<"YES\n";return;}
  20. #define sc(x) scanf("%lld",&x);
  21. string a,b;
  22. int n,m;
  23. vector<vector<int>> g(N);
  24. int cnt[N];
  25. deque<int> d;
  26. bool mark[N];
  27. int mx=0;
  28. void bfs(int st,int e){
  29.     // int p=0;
  30.     d.push_back(st);
  31.     while(d.size()){
  32.         int r=d.front();
  33.         d.pop_front();
  34.         mark[r]=1;
  35.         for(int i:g[r]){
  36.             if(!mark[i] && e!=i){
  37.                 cnt[i]++;
  38.                 mx=max(mx,cnt[i]);
  39.                 d.push_back(i);
  40.             }
  41.         }
  42. // 9 12
  43. // 1 2
  44. // 1 3
  45. // 1 4
  46. // 2 5
  47. // 3 5
  48. // 4 5
  49. // 5 6
  50. // 5 7
  51. // 5 8
  52. // 6 9
  53. // 7 9
  54. // 8 9
  55. // 1 9
  56.     }
  57. }
  58. void Press_Shift_CMD_B(){
  59.     cin>>n>>m;
  60.     for(int i=0,x,y;i<m;i++){
  61.         cin>>x>>y;
  62.         g[x].push_back(y);
  63.     }
  64.     int x,y;
  65.     cin>>x>>y;
  66.     bfs(x,y);
  67.     for(int i=1;i<=n;i++){
  68.         mx=max(mx,cnt[i]);
  69.     }
  70.     int ans=0;
  71.     mark[x]=0;
  72.     mark[y]=0;
  73.     for(int i=1;i<=n;i++){
  74.         if(i==x || y==i)continue;
  75.         if(mark[i] &&mx==cnt[i]){
  76.             ans++;
  77.             mark[i]=0;
  78.             for(int j:g[i]){
  79.                 mark[j]=0;
  80.             }
  81.             for(int j:g[i]){
  82.                 for(int k:g[j]){
  83.                     if(mark[i] && k!=x && k!=y){
  84.                         mark[j]=1;
  85.                         break;
  86.                     }
  87.                 }
  88.             }
  89.         }
  90.         //cout<<cnt[i]<<' ';
  91.     }
  92.  
  93.     // cout<<'\n';
  94.     x=g[x].size()?g[x].size():INT_MAX;
  95.     y=g[y].size()?g[y].size():INT_MAX;
  96.     cout<<min({x,y,ans})<<endl;
  97. }
  98.  
  99. signed main(){
  100.     int t=1;
  101.     // cin>>t;
  102.     while(t--)Press_Shift_CMD_B();
  103.     return 0;
  104. }
Runtime error #stdin #stdout 0.01s 5696KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ktMgVG
language:
C++ (gcc 8.3)
created:
1 year 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!