fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define Fast  ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  3. using namespace std;
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define endl '\n'
  8. #define vi vector<int>
  9. #define int long long
  10. #define vl vector<long long>
  11. #define vii vector<vector<int>>
  12. #define vll vector<vector<ll>>
  13. #define yes {cout << "YES"<<endl; return ;}
  14. #define no {cout << "NO"<<endl; return ;}
  15. #define mun {cout << "-1\n";return;}
  16. #define all(v) v.begin(), v.end()
  17. #define clr(x, val)	memset((x), (val), sizeof(x))
  18. #define allr(v) v.rbegin(), v.rend()
  19. #define cin(v) for (auto &_ : v) cin >> _;
  20. #define cout(v) for (auto &_: v) cout << _ << " " ;
  21. #define make_unique(v) v.erase(unique(all(v)), v.end());
  22. #define PI acos(-1)
  23. //order_of_key(x): returns number of elements strictly less than x
  24. //find_by_order(k): returns iterator to the k-th smallest element (0-indexed)
  25.  
  26. ll gcd(ll a, ll b)      {if (b == 0) return a; return gcd(b, a % b);} //O(log min(a, b))
  27. ll lcmm(ll a,ll b)     {return a/gcd(a,b)*b;}
  28. ll summ(ll n)         {return  n * ( n+1)/2;}
  29.  
  30. ll Abdalraheem () {
  31.     Fast
  32.     return 0;
  33. }
  34. ll Mex(vector<ll>&s)
  35. {
  36.     set<ll>st(s.begin(),s.end());
  37.     ll idx=0;
  38.     for(auto it:st)
  39.     {
  40.         if(it!=idx)return idx;
  41.         idx++;
  42.     }
  43.     return idx;
  44. }
  45. const ll N =5000;
  46. const ll oo =2e18;
  47. const ll MOD =1e9+7;
  48. using Row = vector<ll>;
  49. using Matrix = vector<Row>;
  50. using Tensor = vector<Matrix>;
  51. using HyperTensor = vector<Tensor>;
  52.  
  53. vector<string>v;
  54. vector<int>cost;
  55. map<string,int>mp;
  56.  
  57. struct DSU {
  58.     map<string , string>parent;
  59.     map<string,int> sizes;
  60.     map<string,int>mini;
  61.  
  62.     void init() {
  63.         for (int i =0 ;i <v.size();i++) {
  64.             parent[v[i]] = v[i];
  65.             sizes[v[i]] = 1;
  66.             mini[v[i]] = cost[i];
  67.         }
  68.     }
  69.  
  70.     string find_root(string u ) {
  71.         if (parent[u] == u ) {
  72.             return u;
  73.         }
  74.         return parent[u] = find_root(parent[u]);
  75.     }
  76.  
  77.     void merge(string u , string v) {
  78.         string root_u = find_root(u);
  79.         string root_v = find_root(v);
  80.  
  81.         if (root_u == root_v) return;
  82.  
  83.         if (sizes[root_u] > sizes[root_v]) {
  84.             swap(root_u, root_v);
  85.         }
  86.  
  87.         parent[root_u] = root_v;
  88.         sizes[root_v] += sizes[root_u];
  89.         mini[root_v] = min(mini[root_v], mini[root_u]);
  90.     }
  91. };
  92.  
  93. void solve() {
  94.     int n , k , m;
  95.     cin>>n>>k>>m;
  96.  
  97.     v.resize(n);
  98.     cost.resize(n);
  99.  
  100.     for (int i=0 ;i<n;i++) {
  101.         cin>>v[i];
  102.     }
  103.  
  104.     for (int i=0 ;i<n ;i++) {
  105.         cin>>cost[i];
  106.         mp[v[i]] = i;
  107.     }
  108.  
  109.     DSU d;
  110.     d.init();
  111.  
  112.     for (int i = 0 ; i<k ;i++) {
  113.         int sz;
  114.         cin>>sz;
  115.         int f;
  116.         cin>>f;
  117.         string u = v[f-1];
  118.  
  119.         for (int j =0 ;j < sz -1 ; j++) {
  120.             int vv;
  121.             cin>>vv;
  122.             string o = v[vv-1];
  123.             d.merge(u,o);
  124.         }
  125.     }
  126.     int ans = 0;
  127.     for (int i = 0; i<m ;i++) {
  128.         string s;
  129.         cin>>s;
  130.         string root_s =d.find_root(s);
  131.         ans+= d.mini[root_s];
  132.     }
  133.     cout<<ans;
  134.  
  135. }
  136.  
  137. signed main() {
  138.     Abdalraheem();
  139.     // freopen("where.in", "r", stdin);
  140.     // freopen("where.out", "w", stdout);
  141.     int tt = 1;
  142.     //cin>>tt;
  143.     while (tt--) {
  144.         solve();
  145.     }
  146. }
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mL3Evz
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!