fork download
copy 
  1. #include <iostream>
  2. #include<numeric>
  3. #include<algorithm>
  4. #include<vector>
  5. using namespace std;
  6. #define ll long long
  7. class DSU {
  8. public:
  9.     vector<int>parent;
  10.     //constructor
  11.     DSU(int n = 100) {
  12.         parent.resize(n);
  13.         iota(parent.begin(), parent.end(), 0);
  14.     }
  15.  
  16.  
  17.  
  18.     //find_set function
  19.     int find_set(int x) {
  20.         return (parent[x] == x ? x : (parent[x] = find_set(parent[x])));
  21.     }
  22.  
  23.     //union function
  24.  
  25.     void unite(int x, int y, ll cost[]) {
  26.         x = find_set(x);
  27.         y = find_set(y);
  28.         if (x != y) {
  29.  
  30.             if (cost[x] < cost[y]) {
  31.                 parent[y] = x;
  32.             }
  33.             else {
  34.                 parent[x] = y;
  35.             }
  36.         }
  37.     }
  38.  
  39.  
  40. };
  41. int main() {
  42.  
  43.     int n, k, m;
  44.     cin >> n >> k >> m;
  45.     string s[100009];
  46.     for (int i = 0; i < n; i++) {
  47.         cin >> s[i];
  48.     }
  49.     ll cost[100009];
  50.     for (int i = 1; i <= n; i++) {
  51.         cin >> cost[i];
  52.     }
  53.  
  54.     int x;
  55.     vector<vector<int>> same_meaning;
  56.     same_meaning.resize(k);
  57.     for (int i = 0; i < k; i++) {
  58.         cin >> x;
  59.         for (int j = 0; j < x; j++) {
  60.             int m; cin >> m;
  61.             same_meaning[i].push_back(m);
  62.         }
  63.     }
  64.  
  65.     string message[m];
  66.     for (int i = 0; i < m; i++) {
  67.         cin >> message[i];
  68.     }
  69.  
  70.  
  71.     DSU d(n+5);
  72.  
  73.     for (int i = 0; i < k; i++) {
  74.         int size = same_meaning[i].size();
  75.         for (int x = 0; x < size; x += 2 ) {
  76.             if (x + 1 < size)
  77.                 d.unite(same_meaning[i][x], same_meaning[i][x + 1], cost);
  78.         }
  79.     }
  80.  
  81.  
  82.  
  83.     ll sum = 0;
  84.     for (int i = 0; i < m; i++) {
  85.         string stemp = message[i];
  86.         auto it = find(s, s + m, stemp) - s + 1;
  87.  
  88.  
  89.         sum = (ll)sum + cost[d.find_set(it)];
  90.     }
  91.  
  92.     cout << (ll)sum << endl;
  93.  
  94. }
Success #stdin #stdout 0.01s 7224KB
comments (?)
stdin
copy 
5 4 4
i loser am the second
100 1 1 5 10
1 1
1 3
2 2 5
1 4
i am the second
stdout
copy 
107
https://ideone.com/ZdprPg
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!