oj.uz

Submission #510126

# Submission time Handle Problem Language Result Execution time Memory
510126 2022-01-14T17:58:28 Z Alexandruabcde Harbingers (CEOI09_harbingers) C++14
0 / 100
 2 ms 2636 KB 
#include <bits/stdc++.h>

using namespace std;

ifstream f ("harbingers.in");
ofstream g ("harbingers.out");

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 () {
    f >> N;

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

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

    for (int i = 2; i <= N; ++ i )
        f >> 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 )
        g << dp[i] << " ";

    return 0;
}

Compilation message

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
0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2636 KB Output isn't correct
2 Incorrect 1 ms 2636 KB Output isn't correct
3 Incorrect 1 ms 2636 KB Output isn't correct
4 Incorrect 2 ms 2636 KB Output isn't correct
5 Incorrect 2 ms 2636 KB Output isn't correct
6 Incorrect 1 ms 2636 KB Output isn't correct
7 Incorrect 1 ms 2636 KB Output isn't correct
8 Incorrect 1 ms 2636 KB Output isn't correct
9 Incorrect 1 ms 2636 KB Output isn't correct
10 Incorrect 1 ms 2636 KB Output isn't correct