Submission #707462

#	Time	Username	Problem	Language	Result	Execution time	Memory
707462		He_Huanglu	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1091 ms	19576 KiB

harbingers

#include <bits/stdc++.h>
#define ii pair<int, int>
#define fi first
#define se second
using namespace std;

const int N = 1e5 + 2;
int n, d[N], s[N], speed[N];
long long f[N];
vector <ii> ke[N];

struct CHT
{
    struct line
    {
        long long A, B;
        line() {};
        line(long long A, long long B) : A(A), B(B) {};
        double cut(line l)
        {
            return 1.0 * (l.B - B) / (A - l.A);
        }
        long long get(long long qx)
        {
            return A * qx + B;
        }
    };

    vector <line> vt; stack <line> VT;
    vector <double> x; stack <double> X;
    vector <int> lst; stack <ii> LST;

    void init(line l, int u)
    {
        vt.push_back(l);
        x.push_back(-1e18);
        lst.push_back(u);
    }

    void add(line l, int u)
    {
        while (vt.size() > 1 && l.cut(vt[vt.size() - 2]) <= x.back())
        {
            VT.push(vt.back()); vt.pop_back();
            X.push(x.back()); x.pop_back();
            LST.push({lst.back(), u}); lst.pop_back();
        }
        if(!vt.empty()) x.push_back(l.cut(vt.back()));
        vt.push_back(l);
        lst.push_back(u);
    }

    long long query(long long qx)
    {
        int id = upper_bound(x.begin(), x.end(), qx) - x.begin() - 1;
        return vt[id].get(qx);
    }

    void del(int u)
    {
        if(lst.back() == u)
        {
            vt.pop_back();
            x.pop_back();
            lst.pop_back();
            while (!LST.empty())
            {
                if(LST.top().se != u) break ;
                lst.push_back(LST.top().fi); LST.pop();
                x.push_back(X.top()); X.pop();
                vt.push_back(VT.top()); VT.pop();
            }
        }
    }
} cht;

void dfs(int u, int pre)
{
    for(auto [v, w] : ke[u]) if(v != pre)
    {
        d[v] = d[u] + w;
        f[v] = 1ll * d[v] * speed[v] - cht.query(speed[v]) + s[v];
        cht.add(CHT :: line(d[v], -f[v]), v);
        dfs(v, u);
        cht.del(v);
    }
}

main ()
{
    cin.tie(0)->sync_with_stdio(0);
    if(fopen("task.inp", "r"))
    {
        freopen("task.inp", "r", stdin);
        freopen("wa.out", "w", stdout);
    }
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v, w; cin >> u >> v >> w;
        ke[u].push_back({v, w});
        ke[v].push_back({u, w});
    }
    for(int i = 2; i <= n; i++) cin >> s[i] >> speed[i];
    cht.init(CHT :: line(0, 0), 1);
    dfs(1, 0);
    for(int i = 2; i <= n; i++) cout << f[i] << " ";
}

Compilation message (stderr)

harbingers.cpp:89:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   89 | main ()
      | ^~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:94:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:95:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |         freopen("wa.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 70 / 100