Submission #924968

#	Time	Username	Problem	Language	Result	Execution time	Memory
924968		sleepntsheep	Sightseeing (NOI14_sightseeing)	C++17	25 / 25	1808 ms	262144 KiB

sightseeing

#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 / 4
• Subtask 2: 5 / 5
• Subtask 3: 6 / 6
• Subtask 4: 10 / 10