Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- using ll = long long;
- using ld = long double;
- using ull = unsigned long long;
- constexpr bool typetest = 0;
- constexpr int N = 5e5 + 5;
- constexpr ll Inf = 1e17;
- template <class T>
- void read(T &x)
- {
- x = 0;
- register int c;
- while ((c = getchar()) && (c > '9' || c < '0'))
- ;
- for (; c >= '0' && c <= '9'; c = getchar())
- x = x * 10 + c - '0';
- }
- int m, n, com[N], l(0), x[N];
- ll dp[N], b[N];
- int y, k;
- vector<int> adj[N], nadj[N], s;
- bool ck[N];
- void Read()
- {
- //cin >> n >> m;
- read(n), read(m);
- for (int i = 1; i <= m; ++i)
- {
- int u, v;
- //cin >> u >> v;
- read(u), read(v);
- adj[u].emplace_back(v);
- nadj[v].emplace_back(u);
- }
- m = 0;
- }
- void dfs(int v)
- {
- ck[v] = 1;
- for (auto i : adj[v])
- if (!ck[i])
- dfs(i);
- s.emplace_back(v);
- }
- void dfs_com(int v)
- {
- com[v] = l;
- x[++m] = v;
- for (auto i : nadj[v])
- if (!com[i])
- dfs_com(i);
- }
- void Kosaraju()
- {
- s.reserve(n);
- for (int i = 1; i <= n; ++i)
- if (!ck[i])
- dfs(i);
- while (!s.empty())
- {
- int c = s.back();
- s.pop_back();
- if (com[c])
- continue;
- dp[++l] = -Inf;
- dfs_com(c);
- }
- }
- void Solve()
- {
- Kosaraju();
- for (int i = 1; i <= n; ++i)
- {
- ll v;
- read(v);
- b[com[i]] += v;
- }
- read(y), read(k);
- y = com[y];
- dp[y] = b[y];
- for (int i = 1; i <= n; ++i)
- for (auto t : nadj[x[i]])
- if (com[t] != com[x[i]])
- dp[com[x[i]]] = max(dp[com[x[i]]], dp[com[t]] + b[com[x[i]]]);
- ll ans(-Inf);
- for (int i = 1; i <= k; ++i)
- {
- int v;
- read(v);
- ans = max(ans, dp[com[v]]);
- }
- cout << ans;
- }
- int32_t main()
- {
- ios::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int t(1);
- if (typetest)
- cin >> t;
- for (int _ = 1; _ <= t; ++_)
- {
- //cout << "Case #" << _ << "\n";
- Read();
- Solve();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment