Submission #510130

#	Time	Username	Problem	Language	Result	Execution time	Memory
510130		Alexandruabcde	Harbingers (CEOI09_harbingers)	C++14	30 / 100	141 ms	65540 KiB

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];

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, deque <PLL> D) {
    int st = 0, dr = D.size()-1;
    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 == 0) interval.first = -INF;
        else interval.first = Intersect(D[mij-1], D[mij]);
        if (mij == D.size()-1) 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 (!D.empty())
        dp[Node] = D[ind].first * V[Node] + D[ind].second + dist[Node] * V[Node] + S[Node];

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

    while (D.size() >= 2 && Intersect(D[D.size()-2], D.back()) >= Intersect(D[D.size()-2], dreapta))
        D.pop_back();

    D.push_back(dreapta);

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

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

        Solve(to, D);
    }
}

int main () {
    Read();
    Dfs(1);
    deque <PLL> emp;
    Solve(1, emp);

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

    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'void Solve(int, std::deque<std::pair<long long int, long long int> >)':
harbingers.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         if (mij == D.size()-1) interval.second = INF;
      |             ~~~~^~~~~~~~~~~~~

• Subtask 1: 30 / 100