Tietoverkko

#include <bits/stdc++.h>

#include <utility>

using namespace std;

#define ll long long
#define ull unsigned long long

struct pair_hash {
    inline std::size_t operator()(const std::pair<int,int> & v) const {
        return ((ll)v.first) << 32 | (ll)(unsigned int)v.second;
        //return (ull)v.first+(ull)v.second*31;
    }
};

vector<pair<int, int>>* vecs[200001] = {};
std::unordered_map<pair<int,int>, int, pair_hash> traveled;

ull cur = 0;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;

    for (int i = 1; i < n; i++)
    {
        int a,b,x;
        cin >> a >> b >> x;

        vector<pair<int, int>>* newv;
        if(vecs[a] == nullptr) {
            newv = new auto(vector<pair<int, int>>());
            vecs[a] = newv;
        }
        if(vecs[b] == nullptr) {
            newv = new auto(vector<pair<int, int>>());
            vecs[b] = newv;
        }

        vecs[a]->push_back({b,x});
        vecs[b]->push_back({a,x});
    }

    struct queMem {
        queMem(int id, vector<pair<int,int>> hist, int spd) {
            this->id = id;
            this->hist = std::move(hist);
            this->spd = spd;
        }
        int id;
        vector<pair<int,int>> hist;
        int spd;
    };

    traveled.reserve(n*(n/10));

    for (int i = 1; i <= n; i++) {
        //f id, s hist
        queue<queMem> bfs_queue = {};
        bitset<200000> visited = {};
        bfs_queue.push({i, {}, __INT32_MAX__});
        while(!bfs_queue.empty()){
            const queMem nxt = bfs_queue.front();
            bfs_queue.pop();
            if(visited.test(nxt.id)) continue;
            visited.set(nxt.id);

            int loopSpd = nxt.spd;
            for (auto iter = nxt.hist.end()-1; iter > nxt.hist.begin()-1 ; iter--) {
                auto fndIter = traveled.find(make_pair(nxt.id, iter->first));
                if(fndIter == traveled.end()){
                    cur += loopSpd;
                    //traveled
                    traveled.emplace(std::make_pair(nxt.id, iter->first), loopSpd);
                    traveled.emplace(std::make_pair(iter->first, nxt.id), loopSpd);
                    //vecs
                    vecs[nxt.id]->emplace_back(iter->first, loopSpd);
                    vecs[iter->first]->emplace_back(nxt.id, loopSpd);
                }else if(fndIter->second < loopSpd){
                    cur -= fndIter->second;
                    cur += loopSpd;
                    //traveled
                    traveled.emplace(std::make_pair(nxt.id, iter->first), loopSpd);
                    traveled.emplace(std::make_pair(iter->first, nxt.id), loopSpd);
                    //vecs
                    vecs[nxt.id]->emplace_back(iter->first, loopSpd);
                    vecs[iter->first]->emplace_back(nxt.id, loopSpd);
                }
                loopSpd = min(loopSpd, iter->second);
            }


            for (const auto &item : *vecs[nxt.id]){
                auto vec2 = nxt.hist;
                vec2.emplace_back(nxt.id, nxt.spd);
                bfs_queue.emplace(item.first, vec2, item.second);
            }
        }
    }

    cout << cur;

    flush(std::cout);
}

Test 1

Group: 1, 2, 3

Verdict: ACCEPTED

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED