Submission #700878

#	Time	Username	Problem	Language	Result	Execution time	Memory
700878		Potato3218	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1142 ms	167860 KiB

sightseeing

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt,fma")
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define INF32 (0x3f3f3f3f)
#define INF64 (0x3f3f3f3f3f3f3f3fLL)
#define INF (INF32)
#define PI (3.14159265358979323846)
#define MOD (10e9+7)
#define typeof(x) remove_reference<decltype(x)>::type
#define _picktype(a,b) common_type<typeof(a),typeof(b)>::type
#define rep(i,a,b) for(_picktype((a),(b)) i=(a); i<(b); i++)
#define repr(i,a,b) for(_picktype((a),(b)) i=(a); i>=(b); i--)
#define fori(a,b) rep(i,(a),(b))
#define forj(a,b) rep(j,(a),(b))
#define fork(a,b) rep(k,(a),(b))
#define rfori(a,b) repr(i,(a),(b))
#define rforj(a,b) repr(j,(a),(b))
#define rfork(a,b) repr(k,(a),(b))
#define forit(a,b) for(auto it=(a); it!=(b); it++)
#define rforit(a,b) for(auto it=(a); it!=(b); it--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define mset(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

void impossible() {cout << -1 << endl; exit(0);}
#if defined(_WIN64) || defined(_WIN32)
inline int getchar_unlocked() { return _getchar_nolock(); }
#endif
int getint() {
    int x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}
ll getll() {
    ll x = 0;
    char ch = getchar();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar_unlocked();
    }
    return x;
}
struct CustomHash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
    size_t operator()(pair<uint64_t,uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};

struct DSU {
    vector<int> par;
    DSU(int n) { par.clear(); par.resize(n, -1); }
    int find(int x) { return par[x] < 0 ? x : par[x] = find(par[x]); }
    int root(int x) { return find(x); }
    int parent(int x) { return find(x); }
    bool connected(int x, int y) { return find(x) == find(y); }
    void merge(int x, int y) {
        if ((x = find(x)) == (y = find(y))) return;
        if (par[y] < par[x]) swap(x,y);
        par[x] += par[y];
        par[y] = x;
    }
};

void solve() {
    int V = getint(), E = getint(), Q = getint();
    DSU d = DSU(V);
    DSU d2 = DSU(V);
    vector<int> res(V, -1);
    vector<pair<int, pii>> edges(E);
    fori(0,E) {
        int a = getint(), b = getint(), q = getint();
        a--; b--;
        edges[i] = mp(q, mp(a,b));
    }
    sort(all(edges), greater<pair<int, pii>>());
    fori(0,E) {
        int q = edges[i].fi, a = edges[i].se.fi, b = edges[i].se.se;
        if (d.connected(a, b)) continue;
        if (!d.connected(0, a) && !d.connected(0, b)) {
            d.merge(a,b);
            d2.merge(a,b);
        } else if (d.connected(0, a) && !d.connected(0, b)) {
            res[d2.find(b)] = q;
            d.merge(a,b);
        } else {
            res[d2.find(a)] = q;
            d.merge(a,b);
        }
    }
    fori(0,Q) {
        int x = getint(); x--;
        cout << res[d2.find(x)] << endl;
    }
}

int main()
{
    // ios::sync_with_stdio(0); cin.tie(0); cout.precision(10); cout<<fixed;
    int t = 1;
    // cin>>t;
    while (t--) solve();
}

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