Submission #580470

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
580470	2022-06-21T09:51:40 Z	danikoynov	Harbingers (CEOI09_harbingers)	C++14	70 / 100	1000 ms	31884 KB

harbingers

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int maxn = 1e5 + 10;

int n;
ll depth[maxn], dp[maxn], to_start[maxn], spd[maxn];
vector < pair < int, ll > > g[maxn];

void add_edge(int v, int u, ll d)
{
    g[v].push_back({u, d});
    g[u].push_back({v, d});
}

const double inf = 1e18;
struct line
{
    ll k, m; /// k * x + m

    line(ll _k = 0, ll _m = 0)
    {
        k = _k;
        m = _m;
    }

};
    double intersect(const line &l1, const line &l2)
    {
        if (l1.k == l2.k)
        {
            if (l1.m > l2.m)
                return inf;
            return - inf;
        }
        return (double)(l2.m - l1.m) / (double)(l1.k - l2.k);
    }

struct bunch
{
    vector < pair < int, line > > bh;
    int res_sz;
};

line st[maxn];
int sz;

bunch add_line(ll k, ll m)
{
    line l(k, m);
    bunch cur;
    cur.res_sz = sz;
    while(sz > 1 &&  intersect(st[sz - 1], l) <= intersect(st[sz - 1], st[sz]))
        {
            cur.bh.push_back({sz, st[sz]});
            sz --;
        }
    st[++ sz] = l;
    return cur;
}

void restore_line(bunch cur)
{
    for (int i = 0; i < cur.bh.size(); i ++)
    {
        pair < int, line > tp = cur.bh[i];
        st[tp.first] = tp.second;
    }
    sz = cur.res_sz;
}

ll query(ll x)
{
    /**ll best = inf;
    for (int i = 1; i <= sz; i ++)
    {
        ll cur = st[i].k * x + st[i].m;
        if (cur < best)
            best = cur;
    }
    return best;*/
    int l = 1, r = sz - 1;
    while(l <= r)
    {
        int m = (l + r) / 2;
        if (intersect(st[m], st[m + 1]) <= (double)(x))
            l = m + 1;
        else
            r = m - 1;
    }
    return st[l].k * x + st[l].m;
}

void dfs(int v, int p)
{
    if (v != 1)
    {
        /// calculate answer
        dp[v] = depth[v] * spd[v] + to_start[v] + query(spd[v]);
    }

    /// add line

    bunch cur = add_line(- depth[v], + dp[v]);

    for (pair < int, ll > nb : g[v])
    {
        if (nb.first == p)
            continue;
        depth[nb.first] = depth[v] + nb.second;
        dfs(nb.first, v);
    }

    /// restore lines
    restore_line(cur);

}
void solve()
{
    cin >> n;
    for (int i = 1; i < n; i ++)
    {
        int v, u, d;
        cin >> v >> u >> d;
        add_edge(v, u, d);
    }
    for (int i = 2; i <= n; i ++)
        cin >> to_start[i] >> spd[i];

    dfs(1, - 1);

    for (int i = 2; i <= n; i ++)
        cout << dp[i] << " ";
    cout << endl;
}

int main()
{
    solve();
    return 0;
}

Compilation message

harbingers.cpp: In function 'void restore_line(bunch)':
harbingers.cpp:81:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, line> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for (int i = 0; i < cur.bh.size(); i ++)
      |                     ~~^~~~~~~~~~~~~~~

Subtask #1

70.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4180 KB	Output is correct
2	Correct	6 ms	4912 KB	Output is correct
3	Correct	100 ms	15444 KB	Output is correct
4	Correct	115 ms	20404 KB	Output is correct
5	Correct	168 ms	26532 KB	Output is correct
6	Correct	222 ms	31884 KB	Output is correct
7	Correct	120 ms	15476 KB	Output is correct
8	Execution timed out	1095 ms	21396 KB	Time limit exceeded
9	Execution timed out	1095 ms	16860 KB	Time limit exceeded
10	Execution timed out	1089 ms	23020 KB	Time limit exceeded