Submission #1210439

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

harbingers

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e9, inf = 2e9,MAXN = 3.5e6+1;

const int N = 1e5+1;

signed s[N],v[N],d[N];
vi dp(N);
vector<pair<signed,signed>> edges[N];

struct Line {
    signed m;
    int b;
    int eval(signed x) {
        return 1LL*m*x+b;
    }
};


Line lines[MAXN];
stack<pair<signed,Line>> upds;
signed lft[MAXN],rgt[MAXN];
int ids = 0;

int crenode() {
    lines[ids] = {inf,inf};
    lft[ids] = -1;
    rgt[ids] = -1;
    ids++;
    return ids-1;
}
signed leftchild(signed node) {
    if (lft[node] == -1) lft[node] = crenode();
    return lft[node];
}

signed rightchild(signed node) {
    if (rgt[node] == -1) rgt[node] = crenode();
    return rgt[node];
}
void update(signed node, signed l,signed r,Line& line) {
    if (line.m == inf && line.b == inf) return;
    int m = (l+r) >> 1;
    bool good = lines[node].eval(l) > line.eval(l);
    bool goodmid = lines[node].eval(m) > line.eval(m);
    if (goodmid) {
        upds.push({node,lines[node]});
        swap(lines[node].m,line.m),swap(lines[node].b,line.b);
    }
    if (l == r) return;
    if (goodmid != good) update(leftchild(node),l,m,line);
    else update(rightchild(node),m+1,r,line);
};

int query(signed node,signed l,signed r,const signed x) {
    if (l == r) return lines[node].eval(x);
    int m = (l+r) >> 1;
    if (x <= m) {
        if (lft[node] == -1) return lines[node].eval(x);
        return min(lines[node].eval(x),query(leftchild(node),l,m,x));
    }
    if (rgt[node] == -1) return lines[node].eval(x);
    return min(lines[node].eval(x),query(rightchild(node),m+1,r,x));
}

void rollback(int k) {
    while (k--) {
        lines[upds.top().ff] = upds.top().ss;
        upds.pop();
    }
}

void dfs(int node,int p,int der = 0) {
    d[node] = der;
    if (node > 1) dp[node] = 1LL*s[node]+1LL*v[node]*d[node]+query(0,0,LIM,v[node]);
    else dp[node] = 0;
    int crea = upds.size();
    update(0,0,LIM,{-d[node],dp[node]});
    int crea2 = upds.size();
    for (auto it : edges[node]) {
        if (it.ff == p) continue;
        dfs(it.ff,node,der+it.ss);
    }
    rollback(crea2-crea);
}

void solve() {
    int n;
    cin >> n;
    for (int i=1;i<n;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        edges[a].push_back({b,c});
        edges[b].push_back({a,c});
    }
    for (int i=2;i<=n;i++) cin >> s[i] >> v[i];
    int root = crenode();
    dfs(1,1);
    for (int i=2;i<=n;i++) cout << dp[i] << ' ';
    cout << '\n';
} 

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef Dodi
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    #endif
    int t = 1;
    //cin >> t;
    while (t --> 0) solve();
}

Compilation message (stderr)

harbingers.cpp: In function 'void dfs(long long int, long long int, long long int)':
harbingers.cpp:88:11: error: cannot bind non-const lvalue reference of type 'Line&' to an rvalue of type 'Line'
   88 |     update(0,0,LIM,{-d[node],dp[node]});
      |     ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:51:50: note:   initializing argument 4 of 'void update(int, int, int, Line&)'
   51 | void update(signed node, signed l,signed r,Line& line) {
      |                                            ~~~~~~^~~~