제출 #1177339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1177339		bohun.i	Sightseeing (NOI14_sightseeing)	C++20	25 / 25	1454 ms	209328 KiB

sightseeing

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;

long long d[500500], p[500500], sz[500500];
long long find(long long x) {
    if (x==p[x])return x;
    return p[x]=find(p[x]);
}

void unite(long long x, long long y) {
    x=find(x);
    y=find(y);
    if (x != y) {
        if (sz[x]<sz[y])swap(x,y);
        p[y]=x;
        sz[x]+=sz[y];
    }
}

    vector<pair<long long, long long> >  v1[500500];
void dfs(long long x, long long pr, long long w) {
    d[x]=w;
    for (long long i=0;i<v1[x].size();i++) {
        if (v1[x][i].first!=pr) {
            dfs(v1[x][i].first, x, min(w, v1[x][i].second));
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    long long n, m, q, w, e, k;
    cin >> n >> m >> q;
    vector<pair<long long, pair<long long, long long> > > v;
    for (long long i=0;i<m; i++) {
        cin >> w >> e >> k;
        v.push_back({k, {e, w}});
    }
    for (long long i = 1; i <= n; i++) {
        d[i] = 0;
        sz[i]=1;
        p[i]=i;
    }
    d[0]=10000000000000;
    sort(v.rbegin(), v.rend());
    for (long long i = 0; i < v.size(); i++) {
        if (sz[p[1]]==n)break;
        if (find(v[i].second.second) != find(v[i].second.first)) {
            v1[v[i].second.second].push_back({v[i].second.first, v[i].first});
            v1[v[i].second.first].push_back({v[i].second.second, v[i].first});
       // cout<<"@";
        unite(v[i].second.first, v[i].second.second);
        }
    }
    dfs(1, -1, 1000000000000);
    for (long long i = 1; i <= q; i++) {
        cin>>k;
        cout<<d[k]<<"\n";
    }
    //cout <<"Q"<< endl;
    return 0;
}

• Subtask 1: 4 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10