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;

void do_search(vector<pair<int, int>> vec, const vector<pair<int,int>>& spds, bitset<200000> visited, int curId, int start){
    for (auto e : vec)
    {
        if(visited.test(e.first)) {
            continue;
        }
        visited.set(e.first, true);

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

        vector<pair<int,int>> nspds = spds;
        nspds.push_back(e);

        bitset<200000> visited2 = visited;
        do_search(*vecs[e.first], nspds, visited2, e.first, start);
    }
}

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

Test 2

Group: 2, 3

Verdict: TIME LIMIT EXCEEDED

Test 3

Group: 3

Verdict: TIME LIMIT EXCEEDED