Sadonkorjuu

#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <climits>
#include <regex>
using namespace std;
#define N 100000 + 1
#define inf 1000000
 
// This array stores the distances of the vertices
// from the nearest source
int dist[N];
 
// This Set contains the vertices not yet visited in
// increasing order of distance from the nearest source
// calculated till now
set<pair<int, int> > Q;

int total = 0;
 
// Util function for Multi-Source BFS
void multiSourceBFSUtil(vector<vector<pair<int,int>>> graph, int s)
{
    set<pair<int, int> >::iterator it;
    unsigned int i;
    for (i = 0; i < graph[s].size(); i++) {
        int v = get<0>(graph[s][i]);
        if (dist[s] + 1 < dist[v]) {
 
            // If a shorter path to a vertex is
            // found than the currently stored
            // distance replace it in the Q
            it = Q.find({ dist[v], v });
            Q.erase(it);
            dist[v] = dist[s] + get<1>(graph[s][v]);
            Q.insert({ dist[v], v });
        }
    }
 
    // Stop when the Q is empty -> All
    // vertices have been visited. And we only
    // visit a vertex when we are sure that a
    // shorter path to that vertex is not
    // possible
    if (Q.size() == 0) {
        return;
    }
        
 
    // Go to the first vertex in Q
    // and remove it from the Q
    it = Q.begin();
    int next = it->second;
    Q.erase(it);
 
    multiSourceBFSUtil(graph, next);
}
 
// This function calculates the distance of
// each vertex from nearest source
void multiSourceBFS(vector<vector<pair<int,int>>> graph, int n,
                          vector<int> sources, int S)
{
    // a hash array where source[i] = 1
    // means vertex i is a source
    vector<int> source (n+1);
 
    for (int i = 1; i <= n; i++) {
        source[i] = 0;
    }
        
    for (int i = 0; i <= S - 1; i++) {
        source[sources[i]] = 1;
    }
        
 
    for (int i = 1; i <= n; i++) {
        if (source[i]) {
            dist[i] = 0;
            Q.insert({ 0, i });
        }
        else {
            dist[i] = inf;
            Q.insert({ inf, i });
        }
    }
 
    set<pair<int, int> >::iterator itr;
 
    // Get the vertex with lowest distance,
    itr = Q.begin();
 
    // currently one of the sources with distance = 0
    int start = itr->second;
 
    multiSourceBFSUtil(graph, start);
 
    // adding the distances
    for (int i = 1; i <= n; i++) {
        total += dist[i];
    }
        
}
 
void addEdge(vector<vector<pair<int, int>>> graph, int u, int v, int w)
{
    graph[u].push_back(make_pair(v, w));
    graph[v].push_back(make_pair(u,w));
}
 
// Driver Code
int main()
{
    int n = 0;
    cin >> n;
    int i = 0;
    int paths = n - 1;
    string roles;
    getline(cin >> ws, roles);
    std::regex r("\\s+");
    vector<vector<pair<int,int>>> graph (n-1);
    roles = std::regex_replace(roles, r, "");
    vector<int> scores(n, -1);
    while (i < paths)
    {
        int a, b, c;
        cin >> a >> b >> c;
        addEdge(graph,a, b, c);
        ++i;
    }
    unsigned int J = 0;
    vector<int> sources;
    while (J < roles.length()) {
        if (roles[J] == '0') {
            sources.push_back(J+1);
        }
        J+=1;
    }
    // Sources
    
 
    int S = sizeof(sources) / sizeof(sources[0]);
    vector<int> edges;
    multiSourceBFS(graph, n, sources, S);
    cout << total << endl;
}

Test 1

Group: 1, 2

Verdict: RUNTIME ERROR

Test 2

Group: 1, 2

Verdict: RUNTIME ERROR

Test 3

Group: 1, 2

Verdict: RUNTIME ERROR

Test 4

Group: 1, 2

Verdict: RUNTIME ERROR

Test 5

Group: 1, 2

Verdict: RUNTIME ERROR

Test 6

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 11

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 16

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 17

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 18

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 19

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 20

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

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: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 25

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 26

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED