prateek_5's blog

By prateek_5, history, 3 years ago, In English

Problem

My code

Pandon me, if I'm violating any rule/protocol. I am new here.

#include <iostream>
#include<numeric>
#include<algorithm>
#include<vector>
using namespace std;
#define ll long long
class DSU {
public:
    vector<int>parent;
    //constructor
    DSU(int n = 100) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }



    //find_set function
    int find_set(int x) {
        return (parent[x] == x ? x : (parent[x] = find_set(parent[x])));
    }

    //union function

    void unite(int x, int y, ll cost[]) {
        x = find_set(x);
        y = find_set(y);
        if (x != y) {

            if (cost[x] < cost[y]) {
                parent[y] = x;
            }
            else {
                parent[x] = y;
            }
        }
    }


};
int main() {

    int n, k, m;
    cin >> n >> k >> m;
    string s[100009];
    for (int i = 0; i < n; i++) {
        cin >> s[i];
    }
    ll cost[100009];
    for (int i = 1; i <= n; i++) {
        cin >> cost[i];
    }

    int x;
    vector<vector<int>> same_meaning;
    same_meaning.resize(k);
    for (int i = 0; i < k; i++) {
        cin >> x;
        for (int j = 0; j < x; j++) {
            int m; cin >> m;
            same_meaning[i].push_back(m);
        }
    }

    string message[m];
    for (int i = 0; i < m; i++) {
        cin >> message[i];
    }


    DSU d(n+5);

    for (int i = 0; i < k; i++) {
        int size = same_meaning[i].size();
        for (int x = 0; x < size; x += 2 ) {
            if (x + 1 < size)
                d.unite(same_meaning[i][x], same_meaning[i][x + 1], cost);
        }
    }

  

    ll sum = 0;
    for (int i = 0; i < m; i++) {
        string stemp = message[i];
        auto it = find(s, s + m, stemp) - s + 1;

        
        sum = (ll)sum + cost[d.find_set(it)];
    }

    cout << (ll)sum << endl;

}
  • Vote: I like it
  • -16
  • Vote: I do not like it

| Write comment?