Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define F first
- #define S second
- #define ll long long
- #define ull unsigned long long
- #define ld long double
- #define SELO ""
- #define openfiles ifstream cin("input" SELO ".txt"); ofstream cout("output" SELO ".txt");
- #define faster ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
- #define all(x) x.begin(), x.end()
- using namespace std;
- vector <ll> pos, swords, shields, used, order, pred, loop, hard, mx_Shield, mx_Sword;
- vector <ll> v[200000], rev_v[200000];
- vector <pair <ll, ll> > type;
- vector <ll> new_type;
- vector <ll> new_Graph[200000];
- void dfs1(ll fr)
- {
- used[fr] = 1;
- for(auto to : v[fr])
- if(!used[to])
- dfs1(to);
- order.push_back(fr);
- }
- void dfs2(ll fr)
- {
- used[fr] = 1;
- for(auto to : rev_v[fr])
- if(!used[to])
- dfs2(to);
- hard.push_back(fr);
- }
- void dfs3(ll fr)
- {
- used[fr] = 1;
- if(new_type[fr] == 2)
- pred[fr] = max(pred[fr], mx_Sword[fr] * mx_Shield[fr]);
- for(auto to : new_Graph[fr])
- {
- if(!used[to])
- dfs3(to);
- pred[fr] = max(pred[fr], pred[to]);
- pred[fr] = max(pred[fr], max(mx_Sword[fr] * mx_Shield[to], mx_Shield[fr] * mx_Sword[to]));
- mx_Sword[fr] = max(mx_Sword[fr], mx_Sword[to]);
- mx_Shield[fr] = max(mx_Shield[fr], mx_Shield[to]);
- }
- }
- int main()
- {
- openfiles
- ll n, m, k;
- cin >> n >> m >> k;
- pos.resize(k);
- swords.resize(n);
- shields.resize(n);
- loop.resize(n);
- for(int i = 0; i < k; i++)
- cin >> pos[i];
- for(int i = 0; i < n; i++)
- cin >> swords[i];
- for(int i = 0; i < n; i++)
- cin >> shields[i];
- for(int i = 0; i < m; i++)
- {
- int l, r;
- cin >> l >> r;
- if(l == r)
- loop[l] = 1;
- v[l - 1].push_back(r - 1);
- rev_v[r - 1].push_back(l - 1);
- }
- used.assign(n, 0);
- mx_Shield.assign(n, 0);
- mx_Sword.assign(n, 0);
- type.resize(n);
- for(int i = 0; i < n; i++)
- if(!used[i])
- dfs1(i);
- used.assign(n, 0);
- int cl = 0;
- for(int i = n - 1; i >= 0; i--)
- if(!used[order[i]])
- {
- dfs2(order[i]);
- int tp = 0;
- if(hard.size() > 1 || loop[hard[0]] == 1)
- tp = 2;
- else
- tp = 1;
- for(int j = 0; j < hard.size(); j++)
- {
- type[hard[j]] = {cl, tp};
- mx_Shield[cl] = max(mx_Shield[cl], shields[hard[j]]);
- mx_Sword[cl] = max(mx_Sword[cl], swords[hard[j]]);
- }
- hard.clear();
- new_type.push_back(tp);
- cl++;
- }
- used.assign(n, 0);
- pred.assign(cl, 0);
- for(int i = 0; i < n; i++)
- {
- for(auto j : v[i])
- if(type[j].F != type[i].F)
- new_Graph[type[i].F].push_back(type[j].F);
- }
- for(int i = 0; i < n; i++)
- if(!used[i])
- dfs3(i);
- ll ans = 0;
- for(int i = 0; i < k; i++)
- ans += pred[type[pos[i] - 1].F];
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement