Arcer's blog

By Arcer, history, 6 weeks ago, In English

I was trying 893C - Rumor. My submission is 367279083 in C++. I got a WA8, but I don't understand why. Someone please help. Code:

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m;
    long long r = 0;
    cin >> n >> m;
    vector<int> v(n);
    vector<pair<int, bool>> x(n, {0, false});
    for (int i = 0; i < n; i++) cin >> v[i];
    for (int i = 0; i < n; i++) x[i].first = i + 1;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        if (v[b - 1] < v[a - 1]) x[a - 1].first = b;
        else x[b - 1].first = a;
    }
    map<int, int> ma;
    vector<int> fi;
    for (int i = 0; i < n; i++) {
        int ind = i;
        if (x[i].second == false) {
            while (x[ind].first != ind + 1) {
                x[ind].second = true;
                ind = x[ind].first - 1;
            }
            ma[ind]++;
            if (ma[ind] == 1) fi.push_back(ind);
        }
    }
    for (int i = 0; i < fi.size(); i++) r += v[fi[i]];
    cout << r << endl;
}

int main() {
    int t = 1;
    //cin >> t;
    while (t--) solve();
}
  • Vote: I like it
  • -11
  • Vote: I do not like it

»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

That's because you solving problem wrong, or i just don't understand you code. I solved it like this:

You should find all components in friendship-graph. Then select the smallest amount of gold in each component, sum it, and your answer done! Thats' because, the people in the same component will tell each other, so you can pay only one person, and he will talk to others. Sorry for terrible english, i tried my best.