oj.uz

답안 #130717

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130717 2019-07-16T03:30:21 Z 구재현(#3176) Harbingers (CEOI09_harbingers) C++14
100 / 100
 152 ms 15992 KB 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
typedef pair<int,int> pi;
typedef pair<lint,lint> pii;
 
vector<pi> graph[100005];
 
int n, s[100005], v[100005];
lint dp[100005];
 
pii stk[100005];
 
inline lint func(pii x, int t){
    return x.first * t + x.second;
}
 
inline bool cross(pii a, pii b, pii c){
    return (1.0 * (b.second - a.second) / (a.first - b.first) >= 1.0 * (c.second - b.second) / (b.first - c.first));
}
 
void process(int x, int& piv, int dist){
    int st, ed, m;
    if(x != 1){
        st = 0, ed = piv - 1;
        while (st != ed){
            m = (st + ed)/2;
            if(func(stk[m],v[x]) <= func(stk[m+1],v[x])){
                ed = m;
            }
            else st = m+1;
        }
        dp[x] = func(stk[st],v[x]) + 1ll * dist * v[x] + s[x];
    }
    pii tmp = pii(-dist,dp[x]);
    st = 0, ed = piv-1;
    while (st < ed){
        m = (st + ed) / 2;
        if(cross(stk[m],stk[m+1],tmp)){
            ed = m;
        }
        else st = m+1;
    }
    piv = ed + 1;
}
 
void solve(int x, int piv, int pa, int dist){
    process(x,piv,dist);
    pii bk = stk[piv];
    stk[piv] = pii(-dist,dp[x]);
    for (int i=0; i<graph[x].size(); i++) {
        if(graph[x][i].second != pa){
            solve(graph[x][i].second,piv+1,x,dist + graph[x][i].first);
        }
    }
    stk[piv] = bk;
}
 
int main(){
    scanf("%d",&n);
    for (int i=0; i<n-1; i++) {
        int s,e,x;
        scanf("%d %d %d",&s,&e,&x);
        graph[s].push_back(pi(x,e));
        graph[e].push_back(pi(x,s));
    }
    for (int i=2; i<=n; i++) {
        scanf("%d %d",&s[i],&v[i]);
    }
    solve(1,0,0,0);
    for (int i=2; i<=n; i++) {
        printf("%lld ",dp[i]);
    }
}

Compilation message

harbingers.cpp: In function 'void solve(int, int, int, int)':
harbingers.cpp:53:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<graph[x].size(); i++) {
                   ~^~~~~~~~~~~~~~~~
harbingers.cpp: In function 'int main()':
harbingers.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
harbingers.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&s,&e,&x);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:70:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&s[i],&v[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 6 ms 2936 KB Output is correct
3 Correct 61 ms 8388 KB Output is correct
4 Correct 91 ms 11396 KB Output is correct
5 Correct 109 ms 13664 KB Output is correct
6 Correct 135 ms 15992 KB Output is correct
7 Correct 81 ms 9080 KB Output is correct
8 Correct 149 ms 12660 KB Output is correct
9 Correct 152 ms 14456 KB Output is correct
10 Correct 133 ms 13684 KB Output is correct