Advertisement
jbn6972

Untitled

Nov 30th, 2022
794
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.23 KB | None | 0 0
  1. // Code Written by : John Nixon
  2. // Date: 30:11:2022  Time: 16:35:59
  3. // Copyrights are applicable
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6. #define int long long int
  7. #define mod 1e9 + 7
  8. #define F first
  9. #define S second
  10. #define pb push_back
  11. #define si set<int>
  12. #define vi vector<int>
  13. #define pii pair<int, int>
  14. #define vpi vector<pii>
  15. #define vpp vector<pair<int, pii>>
  16. #define mii map<int, int>
  17. #define mpi map<pii, int>
  18. #define spi set<pii>
  19. #define endl "\n"
  20. #define sz(x) ((int)x.size())
  21. #define all(p) p.begin(), p.end()
  22. #define double long double
  23. #define que_max priority_queue<int>
  24. #define que_min priority_queue<int, vi, greater<int>>
  25. #define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
  26. #define print(a)          \
  27.     for (auto x : a)      \
  28.         cout << x << " "; \
  29.     cout << endl
  30. #define print1(a)    \
  31.     for (auto x : a) \
  32.     cout << x.F << " " << x.S << endl
  33. #define print2(a, x, y)         \
  34.     for (int i = x; i < y; i++) \
  35.         cout << a[i] << " ";    \
  36.     cout << endl
  37. inline int power(int a, int b)
  38. {
  39.     int x = 1;
  40.     while (b)
  41.     {
  42.         if (b & 1)
  43.             x *= a;
  44.         a *= a;
  45.         b >>= 1;
  46.     }
  47.     return x;
  48. }
  49.  
  50. template <typename Arg1>
  51. void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
  52. template <typename Arg1, typename... Args>
  53. void __f(const char *names, Arg1 &&arg1, Args &&...args)
  54. {
  55.     const char *comma = strchr(names + 1, ',');
  56.     cout.write(names, comma - names) << " : " << arg1 << " | ";
  57.     __f(comma + 1, args...);
  58. }
  59. const int N = 200005;
  60.  
  61. void dfs(int s, map<int, vi> g, mii &v)
  62. {
  63.     for (auto i : g[s])
  64.     {
  65.         if (v[i] == 0)
  66.         {
  67.             v[i] = 1;
  68.             dfs(i, g, v);
  69.         }
  70.     }
  71. }
  72.  
  73. vi deleteEdges(int n, int m, int a, int b, vector<vi> edges, vi nodes)
  74. {
  75.     map<int, vi> g;
  76.  
  77.     for (int i = 0; i < m; i++)
  78.     {
  79.         g[edges[i][0]].pb(edges[i][1]);
  80.     }
  81.  
  82.     mii vis;
  83.     for (auto node : nodes)
  84.     {
  85.  
  86.         vis[node] = 0;
  87.     }
  88.     vis[a] = 1;
  89.     dfs(a, g, vis);
  90.  
  91.     int cnt = 0;
  92.     vi ans;
  93.     for (auto i: nodes)
  94.     {
  95.         if (vis[i] == 0)
  96.         {
  97.             continue;
  98.         }
  99.         for (int j = 0; j < g[i].size(); j++)
  100.         {
  101.             if (g[i][j] == b)
  102.             {
  103.                 ans.pb(i);
  104.             }
  105.         }
  106.     }
  107.     sort(all(ans));
  108.     return ans;
  109. }
  110.  
  111. void solve()
  112. {
  113.     int n;
  114.     cin >> n;
  115.     vi ids(n);
  116.     for (int i = 0; i < n; i++)
  117.         cin >> ids[i];
  118.     // print(ids);
  119.  
  120.     int connections;
  121.     cin >> connections;
  122.  
  123.     vector<vi> adj;
  124.     for (int i = 0; i < connections; i++)
  125.     {
  126.         int u, v;
  127.         cin >> u >> v;
  128.         adj.push_back({u, v});
  129.     }
  130.     int expert, noobie;
  131.     cin >> expert >> noobie;
  132.  
  133.     vi ans =  deleteEdges(n, connections, expert, noobie, adj, ids);
  134.     print(ans);
  135. }
  136. int32_t main()
  137. {
  138.     ios_base::sync_with_stdio(0);
  139.     cin.tie(0);
  140.     cout.tie(0);
  141. #ifndef ONLINE_JUDGE
  142.     freopen("input.txt", "r", stdin);
  143.     freopen("output.txt", "w", stdout);
  144. #endif
  145.     clock_t z = clock();
  146.     int t = 1;
  147.     // cin >> t;
  148.     while (t--)
  149.         solve();
  150.     cerr << "Run Time : " << ((double)(clock() - z) / CLOCKS_PER_SEC);
  151.  
  152.     return 0;
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement