Sadonkorjuu

input/code.cpp: In function 'int main()':
input/code.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i=0; i<n-harbors.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~~~

#include <climits>
#include <iostream>
#include <map>
#include <queue>
#include <vector>

using namespace std;
using ll = long long;
using tpl = tuple<int, int, ll>;
vector<int> visited;

class Compare {
    public:
        bool operator() (tpl a, tpl b) {return (get<2>(a) < get<2>(b) && !visited[get<1>(a)]) || visited[get<1>(b)];}
};
using pqueue = priority_queue<tpl, vector<tpl>, Compare>;
vector<int> harbors;
int n;
map<int, pqueue> reachableFrom;
map<int, vector<tpl>> network;
map<int,ll> roadLengths; 

tpl next() {
    ll m = LLONG_MAX;
    map<int,pqueue>::iterator best;
    for (auto it = reachableFrom.begin(); it!= reachableFrom.end(); it++) {
        auto x = (it->second).top();
        // ll t = get<2>((it->second).top());
        while (visited[get<1>(x)]) {
            (it->second).pop();
            if ((it->second).empty())
                break;
            x = (it->second).top();
        } 
        if (get<2>(x) < m && !visited[get<1>(x)]) {
            m = get<2>(x);
            best = it;
        }
    }
    tpl return_val = (best->second).top();
    (best->second).pop();
    
    roadLengths[get<1>(return_val)] = get<2>(return_val);
    for (auto x : network[get<1>(return_val)]) {
        if (get<1>(x) != get<0>(return_val)) {
            reachableFrom[best->first].push({get<0>(x), get<1>(x), roadLengths[get<0>(x)] + get<2>(x)});
        }
        
    }
    return return_val;
}


int main() {
    int a,b,t;
    ll c;
    

    cin >> n;
    visited = vector<int>(n, 0);
    for (int i=0; i<n; i++) {
        cin >> t;
        network[i] = vector<tpl>();
        roadLengths[i] = 0;
        if (t==0) {
            harbors.push_back(i);
            reachableFrom[i] = pqueue();
            visited[i] = 1;
        }
    }
    
    for (int i=0; i<n-1; i++) {
        cin >> a >> b >> c; a--; b--;
        network[a].push_back({a,b,c});
        network[b].push_back({b,a,c});

        if (reachableFrom.count(a)) {
            reachableFrom[a].push({a,b,c});}
        if (reachableFrom.count(b)) {
            reachableFrom[b].push({b,a,c});}
        
    }
    tpl T;
    ll total = 0;
    for (int i=0; i<n-harbors.size(); i++) {
        T = next();
        visited[get<1>(T)] = 1;
    }
    for (int i=0; i<n; i++) {
        total += roadLengths[i];
    }
    cout << total;
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: ACCEPTED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: ACCEPTED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: ACCEPTED