Advertisement
PGSStas

2019.03.18_B

Mar 18th, 2019
124
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define F first
  4. #define S second
  5. #define ll long long
  6. #define ull unsigned long long
  7. #define ld long double
  8. #define SELO ""
  9. #define openfiles ifstream cin("input"  SELO  ".txt"); ofstream cout("output"  SELO  ".txt");
  10. #define faster ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
  11. #define all(x) x.begin(), x.end()
  12.  
  13. using namespace std;
  14.  
  15. vector <ll> pos, swords, shields, used, order, pred, loop, hard, mx_Shield, mx_Sword;
  16. vector <ll> v[200000], rev_v[200000];
  17. vector <pair <ll, ll> > type;
  18. vector <ll> new_type;
  19. vector <ll> new_Graph[200000];
  20.  
  21. void dfs1(ll fr)
  22. {
  23.     used[fr] = 1;
  24.     for(auto to : v[fr])
  25.         if(!used[to])
  26.             dfs1(to);
  27.     order.push_back(fr);
  28. }
  29.  
  30. void dfs2(ll fr)
  31. {
  32.     used[fr] = 1;
  33.     for(auto to : rev_v[fr])
  34.         if(!used[to])
  35.             dfs2(to);
  36.     hard.push_back(fr);
  37. }
  38.  
  39. void dfs3(ll fr)
  40. {
  41.     used[fr] = 1;
  42.     if(new_type[fr] == 2)
  43.         pred[fr] = max(pred[fr], mx_Sword[fr] * mx_Shield[fr]);
  44.     for(auto to : new_Graph[fr])
  45.     {
  46.         if(!used[to])
  47.             dfs3(to);
  48.         pred[fr] = max(pred[fr], pred[to]);
  49.         pred[fr] = max(pred[fr], max(mx_Sword[fr] * mx_Shield[to], mx_Shield[fr] * mx_Sword[to]));
  50.         mx_Sword[fr] = max(mx_Sword[fr], mx_Sword[to]);
  51.         mx_Shield[fr] = max(mx_Shield[fr], mx_Shield[to]);
  52.     }
  53. }
  54.  
  55. int main()
  56. {
  57.     openfiles
  58.     ll n, m, k;
  59.     cin >> n >> m >> k;
  60.     pos.resize(k);
  61.     swords.resize(n);
  62.     shields.resize(n);
  63.     loop.resize(n);
  64.     for(int i = 0; i < k; i++)
  65.          cin >> pos[i];
  66.     for(int i = 0; i < n; i++)
  67.         cin >> swords[i];
  68.     for(int i = 0; i < n; i++)
  69.         cin >> shields[i];
  70.     for(int i = 0; i < m; i++)
  71.     {
  72.         int l, r;
  73.         cin >> l >> r;
  74.         if(l == r)
  75.             loop[l] = 1;
  76.         v[l - 1].push_back(r - 1);
  77.         rev_v[r - 1].push_back(l - 1);
  78.     }
  79.     used.assign(n, 0);
  80.     mx_Shield.assign(n, 0);
  81.     mx_Sword.assign(n, 0);
  82.     type.resize(n);
  83.     for(int i = 0; i < n; i++)
  84.         if(!used[i])
  85.             dfs1(i);
  86.     used.assign(n, 0);
  87.     int cl = 0;
  88.     for(int i = n - 1; i >= 0; i--)
  89.         if(!used[order[i]])
  90.         {
  91.             dfs2(order[i]);
  92.             int tp = 0;
  93.             if(hard.size() > 1 || loop[hard[0]] == 1)
  94.                 tp = 2;
  95.             else
  96.                 tp = 1;
  97.             for(int j = 0; j < hard.size(); j++)
  98.             {
  99.                 type[hard[j]] = {cl, tp};
  100.                 mx_Shield[cl] = max(mx_Shield[cl], shields[hard[j]]);
  101.                 mx_Sword[cl] = max(mx_Sword[cl], swords[hard[j]]);
  102.             }
  103.             hard.clear();
  104.             new_type.push_back(tp);
  105.             cl++;
  106.         }
  107.     used.assign(n, 0);
  108.     pred.assign(cl, 0);
  109.     for(int i = 0; i < n; i++)
  110.     {
  111.         for(auto j : v[i])
  112.             if(type[j].F != type[i].F)
  113.                 new_Graph[type[i].F].push_back(type[j].F);
  114.     }
  115.     for(int i = 0; i < n; i++)
  116.         if(!used[i])
  117.             dfs3(i);
  118.     ll ans = 0;
  119.     for(int i = 0; i < k; i++)
  120.         ans += pred[type[pos[i] - 1].F];
  121.     cout << ans;
  122. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement