oj.uz

Submission #103444

# Submission time Handle Problem Language Result Execution time Memory
103444 2019-03-30T17:56:43 Z SecretAgent007 Sightseeing (NOI14_sightseeing) C++17
25 / 25
 2908 ms 102208 KB 
#include <bits/stdc++.h>
using namespace std;

#define double long double

const int INF = INT_MAX;

vector< vector< pair< int, int > > > Graph;

vector< int > U;

vector< int > dist;

vector< int > S;

int getParents(int a){
    if(U[a] == a) return a;
    else return U[a] = getParents(U[a]);
}

void Union(int a, int b){
    if(S[getParents(a)] < S[getParents(b)]){
        S[getParents(b)] += S[getParents(a)];
        U[getParents(a)] = getParents(b);
    }else{
        S[getParents(a)] += S[getParents(b)];
        U[getParents(b)] = getParents(a);
    }
}

void dfs(int node, int last){
    for(auto a : Graph[node]){
        if(a.first == last) continue;
        dist[a.first] = min(a.second, dist[node]);
        dfs(a.first, node);
    }
}

signed main(){

    int v, e, q;
    scanf("%d%d%d",&v,&e,&q);

    Graph.resize(v+1);
    U.resize(v+1);
    dist.resize(v+1, INF);
    S.resize(v+1, 1);

    vector< tuple<int, int, int> > ve(e);

    for(int i = 0; i <= v; i++) U[i] = i;

    for(int i = 0; i < e ; i++){
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        ve[i] = make_tuple(c,a,b);
    }

    sort(ve.begin(), ve.end(), greater<tuple<int, int, int> >());

    for(int i = 0; i < e; i++){
        auto tup = ve[i];

        int c = get<0>(tup);
        int a = get<1>(tup);
        int b = get<2>(tup);

        if(getParents(a) == getParents(b)) continue;
        else{
            Union(a,b);
            Graph[a].push_back(make_pair(b,c));
            Graph[b].push_back(make_pair(a,c));
        }
    }

    dfs(1,-1);

    while(q--){
        int a;
        scanf("%d", &a);
        printf("%d\n", dist[a]);
    }
}
/*
4 4 2
1 2 10
1 3 30
2 4 20
3 4 5
3
4
*/

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&v,&e,&q);
     ~~~~~^~~~~~~~~~~~~~~~~~~
sightseeing.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&a,&b,&c);
         ~~~~~^~~~~~~~~~~~~~~~~~~
sightseeing.cpp:80:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a);
         ~~~~~^~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 3672 KB Output is correct
2 Correct 36 ms 3192 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2041 ms 63420 KB Output is correct
2 Correct 2908 ms 102208 KB Output is correct