oj.uz

Submission #130843

# Submission time Handle Problem Language Result Execution time Memory
130843 2019-07-16T07:06:19 Z 송준혁(#3172) Harbingers (CEOI09_harbingers) C++14
50 / 100
 251 ms 26400 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pii;

int N;
vector<pii> adj[101010];
LL A[101010], B[101010], ans[101010], D[101010];
int W[101010], H[101010], P[101010];

struct CHT{
    vector<pii> L;

    void push(pii l){
        int t = L.size()-1;
        while(t > 0 && (L[t].second-l.second)*(L[t].first-L[t-1].first) < (L[t-1].second-L[t].second)*(l.first-L[t].first)) L.pop_back(), t--;
        L.push_back(l);
    }

    LL read(LL x){
        if (L.size() == 1) return 0;
        int l=1, r=L.size()-1, ret=0;
        while (l <= r){
            int mid = (l+r)/2;
            if (L[mid-1].second-L[mid].second < x*(L[mid].first-L[mid-1].first)) ret=mid, l = mid+1;
            else r = mid-1;
        }
        return L[ret].first * x + L[ret].second;
    }
} CH[101010];

int dfs(int u, int p){
    W[u] = 1;
    for (pii v : adj[u]){
        if (v.first == p) continue;
        D[v.first] = D[u] + v.second;
        W[u] += dfs(v.first, u);
    }
    sort(adj[u].begin(), adj[u].end(), [&](pii a, pii b){
        if (a.first == p) return false;
        if (b.first == p) return true;
        return W[a.first] < W[b.first];
    });
    if (u != 1) adj[u].pop_back();
    return W[u];
}

void HLD(int u, int p, int r){
    H[u] = r, P[u] = p;
    for (int i=0; i<(int)adj[u].size()-1; i++) HLD(adj[u][i].first, u, adj[u][i].first);
    if (!adj[u].empty()) HLD(adj[u].back().first, u, r);
}

void solve(int u){
    if (u != 1){
        ans[u] = 1ll << 61;
        for (int a=u; a!=0; a=P[H[a]]) if (H[a] != u) ans[u] = min(ans[u], A[u]*D[u] + B[u] - CH[H[a]].read(A[u]));
    }
    CH[H[u]].push(pii(D[u], -ans[u]));
    for (pii v : adj[u]) solve(v.first);
}

int main(){
    scanf("%d", &N);
    for (int i=1; i<N; i++){
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        adj[u].push_back(pii(v, w));
        adj[v].push_back(pii(u, w));
    }
    for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
    dfs(1, 0);
    HLD(1, 0, 1);
    solve(1);
    for (int i=2; i<=N; i++) printf("%lld ", ans[i]);
    return 0;
}

Compilation message

harbingers.cpp: In function 'int main()':
harbingers.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &N);
     ~~~~~^~~~~~~~~~
harbingers.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &u, &v, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:71:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (int i=2; i<=N; i++) scanf("%lld %lld", &B[i], &A[i]);
                              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Correct 9 ms 5624 KB Output is correct
3 Correct 70 ms 14200 KB Output is correct
4 Correct 109 ms 18548 KB Output is correct
5 Correct 143 ms 22264 KB Output is correct
6 Correct 205 ms 26400 KB Output is correct
7 Incorrect 99 ms 15224 KB Output isn't correct
8 Incorrect 251 ms 22268 KB Output isn't correct
9 Incorrect 195 ms 24036 KB Output isn't correct
10 Incorrect 157 ms 23024 KB Output isn't correct