oj.uz

Submission #580466

# Submission time Handle Problem Language Result Execution time Memory
580466 2022-06-21T09:44:38 Z danikoynov Harbingers (CEOI09_harbingers) C++14
20 / 100
 1000 ms 17620 KB 
/**
 ____ ____ ____ ____ ____ ____
||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 - 2], l) <= intersect(st[sz - 2], st[sz - 1]))
        {
            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
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4180 KB Output is correct
2 Correct 10 ms 4692 KB Output is correct
3 Execution timed out 1022 ms 13272 KB Time limit exceeded
4 Execution timed out 1052 ms 14224 KB Time limit exceeded
5 Execution timed out 1077 ms 15952 KB Time limit exceeded
6 Execution timed out 1100 ms 17620 KB Time limit exceeded
7 Execution timed out 1055 ms 13960 KB Time limit exceeded
8 Execution timed out 1092 ms 17432 KB Time limit exceeded
9 Execution timed out 1091 ms 16724 KB Time limit exceeded
10 Execution timed out 1085 ms 17100 KB Time limit exceeded