oj.uz

Submission #527935

# Submission time Handle Problem Language Result Execution time Memory
527935 2022-02-18T19:27:28 Z Yeboi Sightseeing (NOI14_sightseeing) C++14
5 / 25
 2652 ms 262144 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 make_pair(v, 1e18);
        }
        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].first = a;
            par[b].second = 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 << dist[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++)
......
   65 |         rep(i, edges.size()){
      |             ~~~~~~~~~~~~~~~    
sightseeing.cpp:65:9: note: in expansion of macro 'rep'
   65 |         rep(i, edges.size()){
      |         ^~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 3504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1556 ms 144448 KB Output is correct
2 Incorrect 2652 ms 262144 KB Output isn't correct
3 Halted 0 ms 0 KB -