Tietoverkko

#include <algorithm>
#include <iostream>
#include <stack>
#include <vector>

#pragma GCC optimize ("O3")

using namespace std;

vector<struct yhteys> yhteydet;
vector<vector<uint64_t>> naapurit;

int saaria = 1;
vector<uint64_t> saarimaarat;
vector<uint64_t> saaret;

struct yhteys {
    uint64_t a;
    uint64_t b;
    uint64_t nopeus;
};

bool a_comp(struct yhteys a, struct yhteys b)
{
    return a.nopeus < b.nopeus;
}

uint64_t maara(uint64_t tietokone, uint64_t pois, int saari)
{
    uint64_t m = 1;
    saaret[tietokone] = saari;
    for(uint64_t naapuri: naapurit[tietokone]) {
        //cout << tietokone << ": " << naapuri << endl;
        //cout << "MÄÄRÄ " << tietokone << " " << pois << " " << naapuri << endl;
        if(naapuri != pois && naapuri != 0xffffffffffffffff) {
            //cout << "OIKEA NAAPURI" << endl;
            m += maara(naapuri, tietokone, saari);
        }
    }
    return m;
    /*uint64_t m = 0;
    stack<int> tietokoneet, poiss;
    tietokoneet.push(tietokone);
    poiss.push(pois);
    while(!tietokoneet.empty()) {
        tietokone = tietokoneet.top();
        pois = poiss.top();
        tietokoneet.pop();
        poiss.pop();

        m++;
        for(uint64_t naapuri: naapurit[tietokone]) {
            if(naapuri != pois && naapuri != 0xffffffffffffffff) {
                tietokoneet.push(naapuri);
                poiss.push(tietokone);
            }
        }
    }

    return m;*/
}

void paivita_saaret(struct yhteys yhteys)
{
    uint64_t vanha = saarimaarat[saaret[yhteys.a]];
    int uusisaari = saaria;
    saaria++;
    int a = maara(yhteys.a, yhteys.b, uusisaari);
    saarimaarat[uusisaari] = a;
    saarimaarat[saaret[yhteys.b]] = /*maara(yhteys.b, yhteys.a, saaret[yhteys.b])*/ vanha - a;
}

int main()
{
    uint64_t n;
    cin >> n;

    for(uint64_t i = 0; i < n + 1; i++) {
        vector<uint64_t> v;
        naapurit.push_back(v);
        saarimaarat.push_back(0);
    }
    saarimaarat[0] = n;

    for(uint64_t i = 0; i < n - 1; i++) {
        struct yhteys yhteys;
        cin >> yhteys.a >> yhteys.b >> yhteys.nopeus;
        yhteydet.push_back(yhteys);
        naapurit[yhteys.a].push_back(yhteys.b);
        naapurit[yhteys.b].push_back(yhteys.a);
        saaret.push_back(0);
    }

    sort(yhteydet.begin(), yhteydet.end(), a_comp);

    uint64_t summa = 0;
    for(struct yhteys yhteys: yhteydet) {
        naapurit[yhteys.b][distance(naapurit[yhteys.b].begin(), find(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a))] = 0xffffffffffffffff;
        naapurit[yhteys.a][distance(naapurit[yhteys.a].begin(), find(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b))] = 0xffffffffffffffff;

        paivita_saaret(yhteys);

        uint64_t m1 = saarimaarat[saaret[yhteys.b]];

        //remove(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a);
        //remove(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b);

        //cout << "A" << yhteys.nopeus << " " << yhteys.b << " " << yhteys.a << " " << r << endl;
        uint64_t m2 = saarimaarat[saaret[yhteys.a]];
        uint64_t r = m1 * m2 * yhteys.nopeus;
        //cout << "A" << yhteys.nopeus << " " << yhteys.a << " " << yhteys.b << " " << r << endl;
        summa += r;
    }

    cout << summa << endl;
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED