oj.uz

Submission #527936

# Submission time Handle Problem Language Result Execution time Memory
527936 2022-02-18T19:42:05 Z Yeboi Sightseeing (NOI14_sightseeing) C++14
25 / 25
 2446 ms 230064 KB 
#include <bits/stdc++.h>
#define ll long long
#define modi 1000000007
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i,s) for(ll i=0; i<s ; i++)
#define f(i,a,b) for(ll i(a); i<b ; i++)
const ll INF = 1000000000000000000;
const ll N = 500005;
const ll MAXN = 10000000000;    
const ll SQRT = 750;
const ll MOD = 1000000007;
const ll a_max = 1000001;
using namespace std;

ll n, m, q;

struct UFDS{
    vector<pair<ll,ll>> par;
    void init(){
        par.resize(n);
        rep(i, n){
            par[i] = make_pair(i, 1e18);
        }
    }
    pair<ll,ll> find_set(ll v){
        if(v == par[v].first){
            return par[v];
        }
        ll len = par[v].second;
        par[v] = find_set(par[v].first);
        par[v].second = min(par[v].second, len);
        return par[v];
    }
    void merge(ll a, ll b, ll w){
        a = find_set(a).first;
        b = find_set(b).first;
        if(a != b){
            if(a > b){
                swap(a, b);
            }
            par[b] = make_pair(a, w);
        }
    }
    vector<pair<ll,ll>> get(){
        return par;
    }
};
int main(){
    fastio();
    int t;
    t = 1;
    rep(w2, t){
        cin >> n >> m >> q;
        UFDS vec;
        vec.init();
        vector<pair<ll,pair<ll,ll>>> edges;
        rep(i, m){
            ll u, v, w;
            cin >> u >> v >> w;
            --u,--v;
            edges.push_back(make_pair(w, make_pair(u, v)));
        }
        sort(edges.rbegin(), edges.rend());
        rep(i, edges.size()){
            vec.merge(edges[i].second.first, edges[i].second.second, edges[i].first);
        }
        vector<pair<ll,ll>> dist = vec.get();
        rep(i, q){
            ll x;
            cin >> x;
            --x;
            cout << vec.find_set(x).second << endl;
        }
    }
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:5:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(i,s) for(ll i=0; i<s ; i++)
......
   64 |         rep(i, edges.size()){
      |             ~~~~~~~~~~~~~~~    
sightseeing.cpp:64:9: note: in expansion of macro 'rep'
   64 |         rep(i, edges.size()){
      |         ^~~

Subtask #1
4.0 / 4.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2660 KB Output is correct
2 Correct 21 ms 3144 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1478 ms 104676 KB Output is correct
2 Correct 2446 ms 230064 KB Output is correct