Submission #1137463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137463		icoder178	Harbingers (CEOI09_harbingers)	C++20	Compilation error	0 ms	0 KiB

harbingers

#include<iostream>
#include<algorithm>
using namespace std;
#define int long long
const int maxn = 100005;
const double mdiff = 1e-5;
int dp[maxn];
signed n,dst[maxn],rmv[maxn],s[maxn],v[maxn],connl[maxn],connr[maxn],ncnt = 0,chcnt = 0;
pair<signed,int> cht[maxn];
pair<signed,signed> nconn[maxn];
pair<signed,pair<signed,signed> > conn[maxn*2];
inline void fdp(int pos) {
    int l = -5, r = chcnt+5;
    while(l+1 < r) {
        int mid = (l+r)/2;
        bool isDecr;
        if(mid < 0) isDecr = true;
        else if(mid >= chcnt-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]*(int) cht[r].first+(int) v[pos]*(int) dst[pos]+(int) s[pos];
}
inline void prmv(int pos) {
    int l = -5, r = chcnt+5;
    while(l+1 < r) {
        int mid = (l+r)/2;
        bool isV;
        if(mid < 0) isV = true;
        else if(mid >= (chcnt-1)) isV = false;
        else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
        if(isV) l = mid;
        else r = mid;
    }
    rmv[pos] = r+1;
}
void dfs(int pos, int prevP) {
    int ncl = ncnt;
    for(int i = connl[pos]; i < connr[pos]; i++) {
        int targP = conn[i].second.first;
        int newV = conn[i].second.second;
        if(targP != prevP) {
            dst[targP] = dst[pos]+newV;
            fdp(targP);
            prmv(targP);
            nconn[ncnt].first = rmv[targP];
            nconn[ncnt].second = targP;
            ncnt++;
        }
    }
    int ncr = ncnt;
    sort(nconn+ncl,nconn+ncr);
    for(int i = ncr-1; i >= ncl; i--) {
        while(chcnt > nconn[i].first) chcnt--;
        int targP = nconn[i].second;
        cht[chcnt].first = dst[targP];
        cht[chcnt].second = dp[targP];
        chcnt++;
        dfs(targP,pos);
        chcnt--;
    }
    ncnt = ncl;
}
signed main () {
    scanf("%d",&n);
    for(int i = 0; i < n-1; i++) {
        int a,b,c;
        scanf("%d%d%d",&conn[i*2].first,&conn[i*2].second.first,&conn[i*2].second.second);
        conn[i*2+1].first = conn[i*2].second.first;
        conn[i*2+1].second.first = conn[i*2].first;
        conn[i*2+1].second.second = conn[i*2].second.second;
    }
    sort(conn,conn+n*2-2);
    for(int i = 0; i < n*2-2; i++) {
        connr[conn[i].first] = i+1;
    }
    for(int i = n*2-3; i >= 0; i--) {
        connl[conn[i].first] = i;
    }
    for(int i = 2; i <= n; i++) {
        scanf("%d%d",&s[i],&v[i]);
    }
    chcnt++;
    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 'void prmv(long long int)':
harbingers.cpp:36:31: error: 'y3' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                               ^~
harbingers.cpp:36:34: error: 'y2' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                                  ^~
harbingers.cpp:36:48: error: 'x2' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                                                ^~
harbingers.cpp:36:51: error: 'x1' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                                                   ^~
harbingers.cpp:36:70: error: 'y1' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                                                                      ^~
harbingers.cpp:36:84: error: 'x3' was not declared in this scope
   36 |         else isV = (((double) y3-y2)*((double) x2-x1) > ((double) y2-y1)*((double) x3-x2))+mdiff;
      |                                                                                    ^~
harbingers.cpp: In function 'int main()':
harbingers.cpp:70:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
harbingers.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d%d%d",&conn[i*2].first,&conn[i*2].second.first,&conn[i*2].second.second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:86:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         scanf("%d%d",&s[i],&v[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~