CSES - Datatähti 2022 alku - Results
Submission details
Task:Tietoverkko (Network)
Sender:motsgar
Submission time:2021-10-17 00:08:13
Language:C++17
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED10
#2ACCEPTED15
#3ACCEPTED75
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2, 3details
#2ACCEPTED0.01 s2, 3details
#3ACCEPTED0.74 s3details

Compiler report

input/code.cpp: In function 'int main(int, char**)':
input/code.cpp:47:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (depthMap.size() <= e[s])
input/code.cpp:66:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < depthMap[i].size(); j++)
                         ~~^~~~~~~~~~~~~~~~~~~~
input/code.cpp:73:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int k = 0; k < get<1>(computers[depthMap[i][j]]).size(); k++)
                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:75:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for (int l = 0; l < get<1>(computers[depthMap[i][j]])[k].second.size(); l++)
                                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
input/code.cpp:81:43: warning: comparison b

Code

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct DefaultInt
{
    int i = -1;
};

vector<vector<int>> depthMap;

int main(int argc, char **argv)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll total = 0;

    int amount;
    cin >> amount;

    vector<tuple<pair<int, int>, vector<pair<int, vector<pair<int, int>>>>, vector<pair<int, int>>>> computers(amount);

    for (int i = 0; i < amount - 1; i++)
    {
        int a, b, x;
        cin >> a >> b >> x;
        get<2>(computers[a - 1]).push_back(pair<int, int>(b - 1, x));
        get<2>(computers[b - 1]).push_back(pair<int, int>(a - 1, x));
    }

    int x = 0;

    queue<int> q;

    vector<int> z(amount), e(amount);

    z[x] = 1;
    e[x] = 0;
    q.push(x);
    while (!q.empty())
    {
        int s = q.front();
        q.pop(); // solmun s käsittely tähän

        if (depthMap.size() <= e[s])
            depthMap.resize(e[s] + 1);
        depthMap[e[s]].push_back(s);

        for (auto u : get<2>(computers[s]))
        {
            if (z[u.first])
                continue;
            z[u.first] = 1;
            e[u.first] = e[s] + 1;
            q.push(u.first);

            get<0>(computers[u.first]).first = s;         // previous element
            get<0>(computers[u.first]).second = u.second; // distance to previous element
        }
    }

    for (int i = depthMap.size() - 1; i > -1; i--)
    {
        for (int j = 0; j < depthMap[i].size(); j++)
        {
            pair<int, vector<pair<int, int>>> data;
            map<int, DefaultInt> indexLookup;

            int lengthUp = get<0>(computers[depthMap[i][j]]).second;

            for (int k = 0; k < get<1>(computers[depthMap[i][j]]).size(); k++)
            {
                for (int l = 0; l < get<1>(computers[depthMap[i][j]])[k].second.size(); l++)
                {
                    int lengthOne = min(get<1>(computers[depthMap[i][j]])[k].second[l].second, lengthUp);

                    total += ((ll)min(get<1>(computers[depthMap[i][j]])[k].second[l].second, get<1>(computers[depthMap[i][j]])[k].first)) * get<1>(computers[depthMap[i][j]])[k].second[l].first;

                    for (int m = k + 1; m < get<1>(computers[depthMap[i][j]]).size(); m++)
                    {
                        for (int n = 0; n < get<1>(computers[depthMap[i][j]])[m].second.size(); n++)
                        {
                            total += ((ll)min(get<1>(computers[depthMap[i][j]])[k].second[l].second, get<1>(computers[depthMap[i][j]])[m].second[n].second)) * get<1>(computers[depthMap[i][j]])[k].second[l].first * get<1>(computers[depthMap[i][j]])[m].second[n].first;
                        }
                    }

                    if (indexLookup[lengthOne].i == -1)
                    {
                        indexLookup[lengthOne].i = data.second.size();
                        data.second.push_back(make_pair(get<1>(computers[depthMap[i][j]])[k].second[l].first, lengthOne));
                    }
                    else
                        data.second[indexLookup[lengthOne].i].first += get<1>(computers[depthMap[i][j]])[k].second[l].first;
                }
            }

            if (indexLookup[lengthUp].i == -1)
            {
                //cout << "lookup" << endl;
                indexLookup[lengthUp].i = data.second.size();
                data.second.push_back(make_pair(1, lengthUp));
            }
            else
                data.second[indexLookup[lengthUp].i].first++;

            data.first = lengthUp;
            get<1>(computers[get<0>(computers[depthMap[i][j]]).first]).push_back(data);
            /*
            cout << "syvyys: " << i << ", index: " << depthMap[i][j] + 1 << ", ylös etäisyys: " << lengthUp
                 << ", ylös index: " << get<0>(computers[depthMap[i][j]]).first + 1
                 << ", data pituus: " << get<1>(computers[depthMap[i][j]]).size()
                 << "" << endl;
            */
        }
    }

    cout << total << "\n";
}

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: ACCEPTED

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

correct output
1103702320243776

user output
1103702320243776

Test 3

Group: 3

Verdict: ACCEPTED

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

correct output
1080549209850010931

user output
1080549209850010931