Tietoverkko

#include <bits/stdc++.h>
#include <unordered_set>

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*31+v.second;
    }
};

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


ll cur = 0;

vector<pair<int, int>> do_search(vector<pair<int, int>> vec, const vector<pair<int,int>>& spds, bitset<200000> visited, int curId, int start){
    //second speed, first id
    vector<pair<int,int>> to_return = vector<pair<int,int>>(spds);
    ull origSize = to_return.size();
    for (auto e : vec)
    {
        if(visited.test(e.first)) {
            continue;
        }

        visited.set(e.first, true);
        vector<pair<int,int>> nspds = spds;
        nspds.push_back(e);

        int loopSpd = e.second;
        for (auto iter = spds.end()-1; iter != spds.begin()-1; iter--) {
            loopSpd = min(loopSpd, iter->second);
            if(traveled.find({iter->first, e.first}) != traveled.end() || traveled.find({e.first, iter->first}) != traveled.end()) continue;
            cur += loopSpd;
        }

        traveled.insert({start, e.first});
        for (const auto &item : spds){
            traveled.insert({item.first, e.first});
        }
        vector<pair<int, int>> returnedSpds = do_search(*vecs[e.first], nspds, visited, e.first, start);
        to_return.insert(to_return.end(), returnedSpds.begin() + origSize, returnedSpds.end());
    }
    return to_return;
}

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});
    }

    for (int i = 1; i <= n; ++i) {
        auto ptr = vecs[i];
        if(ptr == nullptr) continue;
        bitset<200000> visited = bitset<200000>();
        visited.set(i, true);
        do_search(*ptr, {{i, __INT32_MAX__}}, visited, i, i);
    }

    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