oj.uz

Submission #924964

# Submission time Handle Problem Language Result Execution time Memory
924964 2024-02-10T07:54:46 Z sleepntsheep Sightseeing (NOI14_sightseeing) C++17
0 / 25
 89 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];
basic_string<int> g[N];

// 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].push_back(u);
    g[k].push_back(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);

    for (auto v : g[u])
    {
        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 < 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;
}

Compilation message

sightseeing.cpp: In function 'int main()':
sightseeing.cpp:98:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |     for (int i = 0; i < ord.size(); ++i)
      |                     ~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 6.0

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

Subtask #4
0 / 10.0

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