Submission #1137399

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137399		icoder178	Harbingers (CEOI09_harbingers)	C++20	50 / 100	1096 ms	43644 KiB

harbingers

#include<iostream>
#include<vector>
using namespace std;
#define int long long
const int maxv = (int) 4e18;
const int maxn = 100005;
int n,dp[maxn];
signed dst[maxn],s[maxn],v[maxn];
vector<pair<signed,int> > conn[maxn],cht;
void dfs(int pos, int prevP) {
    if(pos != 1) {
        int l = -5, r = cht.size()+5;
        while(l+1 < r) {
            int mid = (l+r)/2;
            bool isDecr;
            if(mid < 0) isDecr = true;
            else if(mid >= cht.size()-1) isDecr = false;
            else {
                int vl1 = cht[mid].second-(int) v[pos]*(int) cht[mid].first;
                int vl2 = cht[mid+1].second-(int) v[pos]*(int) cht[mid+1].first;
                isDecr = (vl2 < vl1);
            }
            if(isDecr == true) l = mid;
            else r = mid;
        }
        dp[pos] = cht[r].second-(int) v[pos]*cht[r].first+(int) v[pos]*dst[pos]+(int) s[pos];
    }
    vector<pair<bool,pair<signed,int> > > chtop;
    while(cht.size() >= 2) {
        __int128_t x1 = cht[cht.size()-2].first;
        __int128_t y1 = cht[cht.size()-2].second;
        __int128_t x2 = cht[cht.size()-1].first;
        __int128_t y2 = cht[cht.size()-1].second;
        __int128_t x3 = dst[pos];
        __int128_t y3 = dp[pos];
        __int128_t v1 = (y3-y2)*(x2-x1);
        __int128_t v2 = (y2-y1)*(x3-x2);
        if(v1 > v2) break;
        chtop.push_back(make_pair(false,cht.back()));
        cht.pop_back();
    }
    chtop.push_back(make_pair(true,make_pair(dst[pos],dp[pos])));
    cht.push_back(make_pair(dst[pos],dp[pos]));
    for(int i = 0; i < conn[pos].size(); i++) {
        int targP = conn[pos][i].first;
        int newV = conn[pos][i].second;
        if(targP != prevP) {
            dst[targP] = dst[pos]+newV;
            dfs(targP,pos);
        }
    }
    for(int i = chtop.size()-1; i >= 0; i--) {
        if(chtop[i].first == false) cht.push_back(chtop[i].second);
        else cht.pop_back();
    }
}
signed main () {
    scanf("%lld",&n);
    for(int i = 0; i < n-1; i++) {
        int a,b,c;
        scanf("%lld%lld%lld",&a,&b,&c);
        conn[a].push_back(make_pair(b,c));
        conn[b].push_back(make_pair(a,c));
    }
    for(int i = 2; i <= n; i++) {
        scanf("%lld%lld",&s[i],&v[i]);
    }
    dfs(1,-1);
    for(int i = 2; i <= n; i++) {
        printf("%lld ",dp[i]);
    }
    printf("\n");
    return 0;
}

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:66:19: warning: format '%lld' expects argument of type 'long long int*', but argument 2 has type 'int*' [-Wformat=]
   66 |         scanf("%lld%lld",&s[i],&v[i]);
      |                ~~~^      ~~~~~
      |                   |      |
      |                   |      int*
      |                   long long int*
      |                %d
harbingers.cpp:66:23: warning: format '%lld' expects argument of type 'long long int*', but argument 3 has type 'int*' [-Wformat=]
   66 |         scanf("%lld%lld",&s[i],&v[i]);
      |                    ~~~^        ~~~~~
      |                       |        |
      |                       |        int*
      |                       long long int*
      |                    %d
harbingers.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
harbingers.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         scanf("%lld%lld",&s[i],&v[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 50 / 100