Submission #1137421

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137421		icoder178	Harbingers (CEOI09_harbingers)	C++20	0 / 100	84 ms	13128 KiB

harbingers

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int maxv = (int) 4e18;
const int maxn = 100005;
int n,dst[maxn],dp[maxn],rmv[maxn],s[maxn],v[maxn];
vector<pair<int,int> > conn[maxn],cht;
inline void fdp(int pos) {
    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-v[pos]*cht[mid].first;
            int vl2 = cht[mid+1].second-v[pos]*cht[mid+1].first;
            isDecr = (vl2 < vl1);
        }
        if(isDecr == true) l = mid;
        else r = mid;
    }
    dp[pos] = cht[r].second-v[pos]*cht[r].first+v[pos]*dst[pos]+s[pos];
}
inline void prmv(int pos) {
    int l = -5, r = cht.size()+5;
    while(l+1 < r) {
        int mid = (l+r)/2;
        bool isV;
        if(mid < 0) isV = true;
        else if(mid >= ((int) cht.size())-1) isV = false;
        else {
            __int128_t x1 = cht[mid].first;
            __int128_t y1 = cht[mid].second;
            __int128_t x2 = cht[mid+1].first;
            __int128_t y2 = cht[mid+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);
            isV = (v1 > v2);
        }
        if(isV) l = mid;
        else r = mid;
    }
    rmv[pos] = r+1;
}
void dfs(int pos, int prevP) {
    // vector<pair<int,int> > nconn;
    // 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;
    //         fdp(targP);
    //         prmv(targP);
    //         nconn.push_back(make_pair(rmv[targP],targP));
    //     }
    // }
    // vector<pair<int,int> > rmvd;
    // sort(nconn.begin(),nconn.end());
    // for(int i = ((int) nconn.size())-1; i >= 0; i--) {
    //     while(cht.size() > nconn[i].first) {
    //         rmvd.push_back(cht.back());
    //         cht.pop_back();
    //     }
    //     int targP = nconn[i].second;
    //     cht.push_back(make_pair(dst[targP],dp[targP]));
    //     dfs(targP,pos);
    //     cht.pop_back();
    // }
    // for(int i = ((int) rmvd.size())-1; i >= 0; i--) {
    //     cht.push_back(rmvd[i]);
    // }
    for(int i = 0; i < conn[pos].size(); i++) {
        int targP = conn[pos][i].first;
        if(targP != prevP) {
            dfs(targP,pos);
        }
    }
}
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]);
    }
    cht.push_back(make_pair(0,0));
    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:85:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
harbingers.cpp:88:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         scanf("%lld%lld%lld",&a,&b,&c);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:93:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         scanf("%lld%lld",&s[i],&v[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100