Tietoverkko

#include <bits/stdc++.h>

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 v.first+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 {
        int id;
        vector<pair<int,int>> hist;
        int spd;
    };

    for (int i = 1; i <= n; i++) {
        //f id, s hist
        queue<queMem> bfs_queue = {};
        bitset<200001> visited = {};
        bfs_queue.push({i, {}, __INT32_MAX__});
        while(!bfs_queue.empty()){
            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--) {
                loopSpd = min(loopSpd, iter->second);
                auto fndIter = traveled.find({nxt.id, iter->first});
                if(fndIter == traveled.end()){
                    cur += loopSpd;
                    //traveled
                    traveled.insert({{nxt.id, iter->first}, loopSpd});
                    traveled.insert({{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.insert({{nxt.id, iter->first}, loopSpd});
                    traveled.insert({{iter->first, nxt.id}, loopSpd});
                    //vecs
                    vecs[nxt.id]->emplace_back(iter->first, loopSpd);
                    vecs[iter->first]->emplace_back(nxt.id, loopSpd);
                }
            }

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

    cout << cur;

    flush(std::cout);
}

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED