Submission #924964

#	Time	Username	Problem	Language	Result	Execution time	Memory
924964		sleepntsheep	Sightseeing (NOI14_sightseeing)	C++17	0 / 25	89 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];
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 (stderr)

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