CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:EeliH
Submission time:2021-10-06 23:41:49
Language:C++11
Status:READY
Result:10
Feedback
groupverdictscore
#1ACCEPTED10
#20
#30
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#20.06 s2, 3details
#30.25 s3details

Code

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

using namespace std;

vector<struct yhteys> yhteydet;
vector<int> naapurit[200000];

struct yhteys {
    int a;
    int b;
    int nopeus;
    bool kayty;
};

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

int maara(int tietokone, int pois)
{
    int m = 1;
    for(int naapuri: naapurit[tietokone]) {
        //cout << tietokone << ": " << naapuri << endl;
        //cout << "MÄÄRÄ " << tietokone << " " << pois << " " << naapuri << endl;
        if(naapuri != pois && naapuri != -1) {
            //cout << "OIKEA NAAPURI" << endl;
            m += maara(naapuri, tietokone);
        }
    }
    return m;
}

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

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

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

    uint64_t summa = 0;
    for(struct yhteys yhteys: yhteydet) {
        int m1 = maara(yhteys.b, yhteys.a);

        //remove(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a);
        //remove(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b);
        naapurit[yhteys.b][distance(naapurit[yhteys.b].begin(), find(naapurit[yhteys.b].begin(), naapurit[yhteys.b].end(), yhteys.a))] = -1;
        naapurit[yhteys.a][distance(naapurit[yhteys.a].begin(), find(naapurit[yhteys.a].begin(), naapurit[yhteys.a].end(), yhteys.b))] = -1;

        //cout << "A" << yhteys.nopeus << " " << yhteys.b << " " << yhteys.a << " " << r << endl;
        int m2 = (maara(yhteys.a, yhteys.b) - 1);
        int r = m1 * (m2 + 1) * yhteys.nopeus;
        //cout << "A" << yhteys.nopeus << " " << yhteys.a << " " << yhteys.b << " " << r << endl;
        summa += r;
    }

    cout << summa << endl;
}

Test details

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

input
100
1 2 74
1 3 100
2 4 50
3 5 40
...

correct output
88687

user output
88687

Test 2

Group: 2, 3

Verdict:

input
5000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1103702320243776

user output
1794100716608

Test 3

Group: 3

Verdict:

input
200000
1 2 613084013
1 3 832364259
2 4 411999902
3 5 989696303
...

correct output
1080549209850010931

user output
(empty)