Submission #707456

#	Time	Username	Problem	Language	Result	Execution time	Memory
707456		He_Huanglu	Harbingers (CEOI09_harbingers)	C++17	60 / 100	1091 ms	23352 KiB

harbingers

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

const int N = 1e5 + 5;
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; vector <line> VT;
    vector <double> x; vector <double> X;
    vector <int> lst; vector <ii> LST;
    bool ok = 0;

    void add(line l, int u)
    {
        if(!ok)
        {
            ok = 1;
            vt.push_back(l);
            x.push_back(-1e18);
            lst.push_back(u);
            return ;
        }
        while (vt.size() > 1 && l.cut(vt[vt.size() - 2]) <= x.back())
        {
            VT.push_back(vt.back()); vt.pop_back();
            X.push_back(x.back()); x.pop_back();
            LST.push_back({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.back().se == u)
            {
                lst.push_back(LST.back().fi); LST.pop_back();
                x.push_back(X.back()); X.pop_back();
                vt.push_back(VT.back()); VT.pop_back();
            }
        }
    }
} 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(u);
}

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.add(CHT :: line(0, 0), 1);
    dfs(1, 0);
    for(int i = 2; i <= n; i++) cout << f[i] << " ";
}

Compilation message (stderr)

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

• Subtask 1: 60 / 100