Submission #510137

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
510137	2022-01-14T18:07:27 Z	Alexandruabcde	Harbingers (CEOI09_harbingers)	C++14	100 / 100	120 ms	17908 KB

harbingers

#include <bits/stdc++.h>

using namespace std;

constexpr int NMAX = 1e5 + 5;
typedef pair <int, int> PII;
typedef long long LL;
typedef pair <LL, LL> PLL;
constexpr LL INF = 1e16;

int N;
LL dist[NMAX];
int Dad[NMAX];
vector <PII> G[NMAX];

LL dp[NMAX];

LL V[NMAX], S[NMAX];

PLL D[NMAX];
int vf;

long double Intersect (PLL A, PLL B) {
    return 1.0 * (A.second - B.second) / (B.first - A.first);
}

void Read () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    for (int i = 1; i < N; ++ i ) {
        int x, y, c;
        cin >> x >> y >> c;

        G[x].push_back({y, c});
        G[y].push_back({x, c});
    }

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

    dist[1] = 0;
    dp[1] = 0;
}

void Dfs (int node, int dad = -1) {
    Dad[node] = dad;
    for (auto it : G[node]) {
        int to = it.first;
        int c = it.second;

        if (to == dad) continue;

        dist[to] = dist[node] + c;
        Dfs(to, node);
    }
}

void Solve (int Node) {
    int st = 1, dr = vf;
    int ind = -1;

    dp[Node] = dist[Node] * V[Node] + S[Node];

    while (st <= dr) {
        int mij = (st + dr) / 2;
        pair <long double, long double> interval;

        if (mij == 1) interval.first = -INF;
        else interval.first = Intersect(D[mij-1], D[mij]);
        if (mij == vf) interval.second = INF;
        else interval.second = Intersect(D[mij], D[mij+1]);

        if (interval.first > V[Node]) dr = mij - 1;
        else if (interval.second < V[Node]) st = mij + 1;
        else {
            ind = mij;
            break;
        }
    }

    if (vf > 0)
        dp[Node] = D[ind].first * V[Node] + D[ind].second + dist[Node] * V[Node] + S[Node];

    PLL dreapta = {-dist[Node], dp[Node]};

    int initial_vf = vf;
    PLL schimba;

    st = 1;
    dr = vf;
    int new_vf = vf;

    while (st <= dr) {
        int mij = (st + dr) / 2;

        if (Intersect(D[mij-1], D[mij]) >= Intersect(D[mij], dreapta)) {
            new_vf = mij-1;
            dr = mij - 1;
        }
        else st = mij + 1;
    }
    vf = new_vf;

    ++ vf;
    schimba = D[vf];
    D[vf] = dreapta;

    for (auto it : G[Node]) {
        int to = it.first;

        if (to == Dad[Node]) continue;

        Solve(to);
    }

    D[vf] = schimba;
    vf = initial_vf;
}

int main () {
    Read();
    Dfs(1);
    Solve(1);

    for (int i = 2; i <= N; ++ i )
        cout << dp[i] << " ";

    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	2636 KB	Output is correct
2	Correct	3 ms	3064 KB	Output is correct
3	Correct	38 ms	9088 KB	Output is correct
4	Correct	55 ms	12376 KB	Output is correct
5	Correct	74 ms	15048 KB	Output is correct
6	Correct	96 ms	17908 KB	Output is correct
7	Correct	49 ms	10120 KB	Output is correct
8	Correct	120 ms	14700 KB	Output is correct
9	Correct	110 ms	16432 KB	Output is correct
10	Correct	95 ms	15488 KB	Output is correct