Блог пользователя Arcer

Автор Arcer, история, 2 месяца назад, По-английски

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();
}
  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

»
2 месяца назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.