oj.uz

Submission #924966

# Submission time Handle Problem Language Result Execution time Memory
924966 2024-02-10T07:56:13 Z sleepntsheep Sightseeing (NOI14_sightseeing) C++17
15 / 25
 1150 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];
array<int, 3> el[N];
int g[N][2];

// krt

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);
    for (int i = 0; i < m; ++i) cin >> el[i][1] >> el[i][2] >> el[i][0];
    sort(el, el+m, 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 42 ms 185172 KB Output is correct
2 Correct 37 ms 185180 KB Output is correct

Subtask #2
5.0 / 5.0

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

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 194496 KB Output is correct
2 Correct 60 ms 194264 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1150 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -