Submission #707157

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
707157	2023-03-08T14:15:05 Z	He_Huanglu	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1000 ms	20100 KB

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; stack <line> VT;
    vector <double> x; stack <double> X;
    vector <int> lst; stack <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())
        {
//            cout << u << " " << lst.back() << "**\n";
            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);
//        cout << u << "**\n";
//        for(int o : lst) cout << o << " ";
//        cout << "\n\n";
    }

    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)
    {
//        cout << u << "%%\n";
//        for(int o : lst) cout << o << " ";
//        cout << "\n\n";
        if(lst.back() == u)
        {
            vt.pop_back();
            x.pop_back();
            lst.pop_back();
            while (!LST.empty())
            {
                if(LST.top().se != u) break ;
//                cout << u << " " << LST.top() << "^^\n";
                lst.push_back(LST.top().fi); LST.pop();
                x.push_back(X.top()); X.pop();
                vt.push_back(VT.top()); VT.pop();
            }
        }
//        cout << u << " :\n";
//        for(double o : lst) cout << o << " ";
//        cout << "\n\n";
    }
} 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

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

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2644 KB	Output is correct
2	Correct	3 ms	3156 KB	Output is correct
3	Correct	33 ms	10248 KB	Output is correct
4	Correct	65 ms	13564 KB	Output is correct
5	Correct	72 ms	16840 KB	Output is correct
6	Correct	90 ms	20100 KB	Output is correct
7	Correct	49 ms	10144 KB	Output is correct
8	Execution timed out	1084 ms	13940 KB	Time limit exceeded
9	Execution timed out	1065 ms	11340 KB	Time limit exceeded
10	Execution timed out	1052 ms	15424 KB	Time limit exceeded