oj.uz

Submission #869074

# Submission time Handle Problem Language Result Execution time Memory
869074 2023-11-03T05:18:52 Z sleepntsheep Harbingers (CEOI09_harbingers) C++17
70 / 100
 1000 ms 29520 KB 
#include <cstdio>
#include <stack>
#include <cstring>
#include <cassert>
#include <string>
#include <deque>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
#include <utility>
using namespace std;
using ll = long long;
using ld = long double;
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false)

#define N 200005
#define ALL(x) x.begin(), x.end()

struct line
{
    ll m, c;
    line(ll m, ll c) : m(m), c(c) {}
    ll operator[](ll x) { return m*x+c; }
    ll intersect(line &l) { return (ld)(c-l.c)/(l.m-m); }
};


ostream& operator<<(ostream &out, line k)
{
    out << '{'<<k.m << ", "  <<k.c<<'}';
    return out;
}

int n, s[N], v[N];
ll rt[N], dp[N];
vector<pair<int, int>> g[N];

struct cht_rollback : deque<line>
{
    stack<tuple<int, line>> saves;
    stack<int> at;

    void pop_back_save()
    {
        saves.emplace(0, back());
        pop_back();
    }

    void push_back_save(line k)
    {
        saves.emplace(1, k);
        push_back(k);
    }

    void rollback()
    {
        while (saves.size() > at.top())
        {
            auto [t, k] = saves.top(); saves.pop();
            if (t) pop_back();
            else push_back(k);
        }
        at.pop();
    }

    void add(line k)
    {
        at.push(saves.size());
        while (size() > 1)
        {
            if ((back().m == k.m && back().c <= k.c) ||
                    back().intersect((*this)[size()-2]) > back().intersect(k)) pop_back_save();
            else break;
        }
        if (size() && back().m == k.m && back().c >= k.c) return;
        push_back_save(k);
    }

    ll qry(ll x)
    {
        if (empty()) return 0;
        int l = 0, r = size() - 2, z = size() - 1;
        for (;l <= r;)
        {
            int m = (l+r)/2;
            if ((*this)[m].intersect((*this)[m+1]) < x) l=m+1;
            else r=m-1, z = m;
        }
        return (*this)[z][x];
    }

};

cht_rollback cht;

void dfs(int u, int p)
{
    //cerr << "E " << u << ' ' << cht.size(); for (auto x : cht) cout << x<<' '; cout<<endl;
    dp[u] = s[u] + 1ll*v[u]*rt[u] - cht.qry(v[u]);
    dp[1] = 0;
    cht.add(line{rt[u], -dp[u]});
    for (auto [w, v] : g[u]) if (v != p)
    {
        rt[v] = rt[u] + w;
        dfs(v, u);
    }
    cht.rollback();
}

int main()
{
    ShinLena;
    cin >> n;
    for (int u, v, w, i = 1; i < n; ++i) cin >> u >> v >> w, g[u].emplace_back(w, v), g[v].emplace_back(w, u);
    for (int i = 2; i <= n; ++i) cin >> s[i] >> v[i];
    dfs(1, 1);
    for (int i = 2; i <= n; ++i) cout << dp[i] << ' ';

    return 0;
}

Compilation message

harbingers.cpp: In member function 'void cht_rollback::rollback()':
harbingers.cpp:59:29: warning: comparison of integer expressions of different signedness: 'std::stack<std::tuple<int, line> >::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   59 |         while (saves.size() > at.top())
      |                ~~~~~~~~~~~~~^~~~~~~~~~

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 3 ms 9360 KB Output is correct
3 Correct 39 ms 17216 KB Output is correct
4 Correct 50 ms 21076 KB Output is correct
5 Correct 59 ms 25224 KB Output is correct
6 Correct 91 ms 29520 KB Output is correct
7 Correct 46 ms 15884 KB Output is correct
8 Execution timed out 1054 ms 19048 KB Time limit exceeded
9 Execution timed out 1027 ms 15896 KB Time limit exceeded
10 Execution timed out 1062 ms 20880 KB Time limit exceeded