### prateek_5's blog

By prateek_5, history, 5 weeks ago, 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;
for (int i = 0; i < n; i++) {
cin >> s[i];
}
ll cost;
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;

} Comments (3)
 » here's my code link:https://codeforces.com/contest/959/submission/126589104 see if you can get an idea..
 » The biggest problem you have is that your code is an order of magnitude more complicated than it needs to be. It looks like it does the following:For ever group, build some kind of tree such that the root is the smallest element. Work your way up to the top to find the best replacement word, for every word in the sentence.In theory this will work, but it's quite complicated, and for cases where everything is all in one group, notice that it's possible to get an $n^2$ explosion which will definitely time out for $10^5$. Notice how instead of keeping track of a words parent, every element can instead just point to the root. And notice how instead of using a graph-like data structure with a root, all that you really care about is the minimum value for a group, which can just be held in an array the size of the number of groups!
 » This solution is pretty straightforward. I'm not sure DSU is the best way to understand it.Essentially, each group of words is in a component, meaning it is a collection of elements that go together. For each word, make a map and for each string (or hash the string if its easier) store that string's component number. Then, store an array that calculates the string with the min cost in each component. For each string that you're given, retrieve the component number from the map, and then add the newly stored array's min component cost. Finally, print out your summations.