oj.uz

Submission #924968

# Submission time Handle Problem Language Result Execution time Memory
924968 2024-02-10T07:58:00 Z sleepntsheep Sightseeing (NOI14_sightseeing) C++17
25 / 25
 1808 ms 262144 KB 
#include <iostream>
#include <stack>
#include <numeric>
#include <fstream>
#include <iomanip>
#include <cmath>
#include <cassert>
#include <cstring>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#include <complex>

using u32 = unsigned;
using i32 = int;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;

using namespace std;
using pt = complex<f80>;
#define ALL(x) begin(x), end(x)
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
#define N 5500005
#define V 500005

int n, m, q, l, cst[N], ans[V];
int g[N][2];

// krt & lcarmq & O(ackerman) rmq

int arpa[N+N];

int __find(int u) { return arpa[u] == u ? u : arpa[u] = __find(arpa[u]); }

int _par[N];

int _find(int u) { return _par[u] == u ? u : _par[u] =  _find(_par[u]); }

void consider(int w, int u, int v)
{
    if ((u = _find(u)) == (v = _find(v))) return;
    int k = ++l;
    g[k][0] = u; g[k][1] = v;
    _par[u] = _par[v] = k;
    cst[k] = w;
}

int timer, occ[N];
vector<int> dep, ord;

void tour(int u, int d)
{
    occ[u] = timer++;
    ord.push_back(u);
    dep.push_back(d);

    if (g[u][0])
    for (auto v : {g[u][0], g[u][1]})
    {
        tour(v, d+1);
        ++timer;
        ord.push_back(u);
        dep.push_back(d);
    }

}

basic_string<pair<int, int>> attached[N];

int main()
{
    ShinLena;
    cin >> n >> m >> q;
    l = n;
    iota(_par, _par+n+m+1, 0);
    {
        vector<array<int, 3>> el(m);
        for (int i = 0; i < m; ++i) cin >> el[i][1] >> el[i][2] >> el[i][0];
        sort(ALL(el), greater());
        for (int i = 0; i < m; ++i) consider(el[i][0], el[i][1], el[i][2]);
    }

    tour(l, 1);

    for (int i = 0, bb; i < q; ++i)
    {
        cin >> bb;
        auto [l, r] = minmax(occ[1], occ[bb]);
        attached[r].push_back({l, i});
    }


    iota(arpa, arpa+ord.size() + 1, 0);
    stack<int> st;
    for (int i = 0; i < (int)ord.size(); ++i)
    {
        while (st.size() and dep[st.top()] >= dep[i]) arpa[__find(st.top())] = i, st.pop();
        st.push(i);
        for (auto [ql, qid] : attached[i]) ans[qid] = ord[__find(ql)];
    }

    for (int i = 0; i < q; ++i) cout << cst[ans[i]] << '\n';

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 183124 KB Output is correct
2 Correct 37 ms 183044 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 183132 KB Output is correct
2 Correct 37 ms 183132 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 189172 KB Output is correct
2 Correct 54 ms 189804 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1164 ms 262144 KB Output is correct
2 Correct 1808 ms 262144 KB Output is correct