oj.uz

Submission #491483

# Submission time Handle Problem Language Result Execution time Memory
491483 2021-12-02T17:04:22 Z blue Harbingers (CEOI09_harbingers) C++17
20 / 100
 1000 ms 25152 KB 
#include <iostream>
#include <vector>
using namespace std;

using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;

#define pb push_back

const int maxN = 100'000;
const int lgN = 17;

ll INF = 2'000'000'001;

vector<pair<int, ll>> edge[1+maxN];

vll S(1+maxN), V(1+maxN);
vi P(1+maxN);
vll D(1+maxN, 0);

vi ord;

void dfs(int u, int p)
{
    ord.push_back(u);
    P[u] = p;
    for(auto x: edge[u])
    {
        int v = x.first;
        ll d = x.second;
        if(v == p) continue;
        D[v] = D[u] + d;
        dfs(v, u);
    }
}





struct line
{
    ll a;
    ll b;

    ll eval(ll x)
    {
        return a*x + b;
    }
};

bool intersect_comp(line A, line B, line C, line D)
{
    //A.a * x + A.b == B.a * x + B.b, x = (B.b - A.b)/(A.a - B.a)

    ll mul = 1;
    if(A.a - B.a < 0) mul *= -1;
    if(C.a - D.a < 0) mul *= -1;
    return mul * (B.b - A.b) * (C.a - D.a) < mul * (D.b - C.b) * (A.a - B.a);
}

vector<line> cht(1+maxN);
int cht_anc[1+maxN][1+lgN];

void insert_line(int u, line l)
{
    int a = cht_anc[u][0];
    for(int e = lgN; e >= 0; e--)
    {
        int v = cht_anc[a][e];
        if(v == 1) continue;
        int w = cht_anc[v][0];
        ll mul = 1;
        if(!intersect_comp(cht[w], cht[v], cht[v], l))
            a = w;
    }

    cht_anc[u][0] = a;
    for(int e = 1; e <= lgN; e++)
        cht_anc[u][e] = cht_anc[ cht_anc[u][e-1] ][e-1];
}

ll query(int u, ll x)
{
    for(int e = lgN; e >= 0; e--)
    {
        int v = cht_anc[u][e];
        if(v == 1) continue;
        int w = cht_anc[v][0];

        ll mul = 1;
        if(cht[w].a - cht[v].a < 0) mul = -1;

        if(x * (cht[w].a - cht[v].a) * mul <= (cht[v].b - cht[w].b) * mul)
            u = w;
    }

    return cht[u].eval(x);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N;
    cin >> N;

    for(int i = 1; i <= N-1; i++)
    {
        int u, v;
        ll d;
        cin >> u >> v >> d;

        edge[u].pb({v, d});
        edge[v].pb({u, d});
    }

    for(int i = 2; i <= N; i++) cin >> S[i] >> V[i];


    dfs(1, 1);


    for(int i = 1; i <= N; i++)
        for(int e = 0; e <= lgN; e++)
            cht_anc[i][e] = i;

    insert_line(1, {0, 0});

    vll dp(1+N, INF);
    dp[1] = 0;
    for(int u: ord)
    {
        if(u == 1) continue;

        dp[u] = ll(S[u]) + ll(V[u])*ll(D[u]) + query(P[u], V[u]);
        insert_line(u, {-D[u], dp[u]});
        for(int v = P[u]; 1; v = P[v])
        {
            dp[u] = min(dp[u], S[u] + V[u]*D[u] + (-D[v] * V[u] + dp[v]));
            if(v == 1) break;
        }
    }

    for(int i = 2; i <= N; i++) cout << dp[i] << ' ';
    cout << '\n';
}

Compilation message

harbingers.cpp: In function 'void insert_line(int, line)':
harbingers.cpp:74:12: warning: unused variable 'mul' [-Wunused-variable]
   74 |         ll mul = 1;
      |            ^~~

Subtask #1
20.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6988 KB Output is correct
2 Correct 16 ms 7500 KB Output is correct
3 Execution timed out 1082 ms 14316 KB Time limit exceeded
4 Execution timed out 1081 ms 17916 KB Time limit exceeded
5 Execution timed out 1084 ms 21528 KB Time limit exceeded
6 Execution timed out 1088 ms 25152 KB Time limit exceeded
7 Execution timed out 1087 ms 17544 KB Time limit exceeded
8 Execution timed out 1084 ms 22384 KB Time limit exceeded
9 Execution timed out 1092 ms 22964 KB Time limit exceeded
10 Execution timed out 1090 ms 22332 KB Time limit exceeded