oj.uz

Submission #321550

# Submission time Handle Problem Language Result Execution time Memory
321550 2020-11-12T18:02:00 Z arujbansal Sightseeing (NOI14_sightseeing) C++17
25 / 25
 2276 ms 202728 KB 
#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define setIO(i, o) freopen(i, "r", stdin), freopen(o, "w", stdout)
#define seed() srand(chrono::steady_clock::now().time_since_epoch().count())
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int) (x).size()
#define lc(i) 2*i
#define rc(i) 2*i+1
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using vvi = vector<vi>;
using vb = vector<bool>;
using vvb = vector<vb>;

ll rng() {
    ll a = rand();
    ll b = rand();
    return a * (RAND_MAX + 1ll) + b;
}

const int N = 5e5 + 5, MOD = 1e9 + 7, INF = 1e9 + 5;
vii g[N];
int mn[N];

struct DSU {
    int n;
    vector<int> par, s;

    void init(int x) {
        n = x;
        par.resize(n);
        iota(all(par), 0);
        s.assign(n, 1);
    }

    int get(int x) {
        if (par[x] == x) return x;
        return par[x] = get(par[x]);
    }

    bool unite(int x, int y) {
        x = get(x);
        y = get(y);
        if (x == y) return false;
        if (s[x] < s[y]) swap(x, y);
        s[x] += s[y];
        par[y] = x;
        return true;
    }

    int getSz(int x) {
        x = get(x);
        return s[x];
    }
};

struct Edge {
    int u, v, w;

    Edge(int u, int v, int w) : u(u), v(v), w(w) {}

    bool operator<(const Edge &other) const {
        return w > other.w;
    }
};

void dfs(int u = 0, int p = -1) {
    for (const auto &[v, w] : g[u]) {
        if (v == p) continue;

        mn[v] = min(mn[u], w);
        dfs(v, u);
    }
}

void solve() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<Edge> edges;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;

        edges.eb(u, v, w);
    }

    sort(all(edges));

    DSU sites;
    sites.init(n);

    for (const auto &[u, v, w] : edges) {
       if (!sites.unite(u, v)) continue;
       g[u].eb(v, w);
       g[v].eb(u, w);
    }

    mn[0] = INF;
    dfs();

    while (q--) {
        int v;
        cin >> v;
        v--;

        cout << mn[v] << "\n";
    }
}

signed main() {
    FAST_IO;
#ifdef arujbansal_local
    setIO("input.txt", "output.txt");
#endif

    seed();

    int tc = 1;
//    cin >> tc;
    while (tc--) solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12160 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12140 KB Output is correct
2 Correct 8 ms 12140 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 14568 KB Output is correct
2 Correct 32 ms 14180 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1525 ms 66840 KB Output is correct
2 Correct 2276 ms 202728 KB Output is correct