Dang_Quan_10_Tin

ATM

Sep 9th, 2021
1,482
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5. using ld = long double;
  6. using ull = unsigned long long;
  7.  
  8. constexpr bool typetest = 0;
  9. constexpr int N = 5e5 + 5;
  10. constexpr ll Inf = 1e17;
  11.  
  12. template <class T>
  13. void read(T &x)
  14. {
  15.     x = 0;
  16.     register int c;
  17.     while ((c = getchar()) && (c > '9' || c < '0'))
  18.         ;
  19.     for (; c >= '0' && c <= '9'; c = getchar())
  20.         x = x * 10 + c - '0';
  21. }
  22.  
  23. int m, n, com[N], l(0), x[N];
  24. ll dp[N], b[N];
  25. int y, k;
  26. vector<int> adj[N], nadj[N], s;
  27. bool ck[N];
  28.  
  29. void Read()
  30. {
  31.     //cin >> n >> m;
  32.     read(n), read(m);
  33.     for (int i = 1; i <= m; ++i)
  34.     {
  35.         int u, v;
  36.         //cin >> u >> v;
  37.         read(u), read(v);
  38.         adj[u].emplace_back(v);
  39.         nadj[v].emplace_back(u);
  40.     }
  41.     m = 0;
  42. }
  43.  
  44. void dfs(int v)
  45. {
  46.     ck[v] = 1;
  47.     for (auto i : adj[v])
  48.         if (!ck[i])
  49.             dfs(i);
  50.     s.emplace_back(v);
  51. }
  52.  
  53. void dfs_com(int v)
  54. {
  55.     com[v] = l;
  56.     x[++m] = v;
  57.     for (auto i : nadj[v])
  58.         if (!com[i])
  59.             dfs_com(i);
  60. }
  61.  
  62. void Kosaraju()
  63. {
  64.     s.reserve(n);
  65.     for (int i = 1; i <= n; ++i)
  66.         if (!ck[i])
  67.             dfs(i);
  68.  
  69.     while (!s.empty())
  70.     {
  71.         int c = s.back();
  72.         s.pop_back();
  73.  
  74.         if (com[c])
  75.             continue;
  76.  
  77.         dp[++l] = -Inf;
  78.         dfs_com(c);
  79.     }
  80. }
  81.  
  82. void Solve()
  83. {
  84.     Kosaraju();
  85.  
  86.     for (int i = 1; i <= n; ++i)
  87.     {
  88.         ll v;
  89.         read(v);
  90.         b[com[i]] += v;
  91.     }
  92.  
  93.     read(y), read(k);
  94.     y = com[y];
  95.     dp[y] = b[y];
  96.  
  97.     for (int i = 1; i <= n; ++i)
  98.         for (auto t : nadj[x[i]])
  99.             if (com[t] != com[x[i]])
  100.                 dp[com[x[i]]] = max(dp[com[x[i]]], dp[com[t]] + b[com[x[i]]]);
  101.  
  102.     ll ans(-Inf);
  103.  
  104.     for (int i = 1; i <= k; ++i)
  105.     {
  106.         int v;
  107.         read(v);
  108.         ans = max(ans, dp[com[v]]);
  109.     }
  110.     cout << ans;
  111. }
  112.  
  113. int32_t main()
  114. {
  115.     ios::sync_with_stdio(0);
  116.     cin.tie(0);
  117.     cout.tie(0);
  118.     int t(1);
  119.     if (typetest)
  120.         cin >> t;
  121.     for (int _ = 1; _ <= t; ++_)
  122.     {
  123.         //cout << "Case #" << _ << "\n";
  124.         Read();
  125.         Solve();
  126.     }
  127. }
Advertisement
Add Comment
Please, Sign In to add comment