Submission #1195204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195204		ByeWorld	Harbingers (CEOI09_harbingers)	C++20	100 / 100	119 ms	27244 KiB

harbingers

#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+10;
const int SQRT = 25;
const int MAXA = 50;
const int LOG = 27;
const int INF = 4e18+10;
const ld EPS = 1e-6;
const int MOD = 998244353;
int sum(int a, int b){ return (a+b)%MOD; }
void chsum(int &a, int b){ a = (a+b)%MOD; }
void chsub(int &a, int b){ a = (a+MOD-b)%MOD; }
int mul(int a, int b){ return (a*b)%MOD; }
void chmul(int &a, int b){ a = (a*b)%MOD; }
void chmn(int &a, int b){ a = min(a, b); }
void chmx(auto &a, auto b){ a = max(a, b); }
const vector <int> dx = {-1, 1, 0, 0};
const vector <int> dy = {0, 0, 1, -1};

int n, dp[MAXN], dep[MAXN], s[MAXN], v[MAXN];
vector <pii> adj[MAXN];
vector <int> tree[MAXN];
vector <int> vec;

struct Line {
    int m, c;
    int getY(int x){ return m*x+c; }
};
bool cmp(Line a, Line b, Line z){
    int A = b.c-a.c, B = a.m-b.m;
    int C = z.c-b.c, D = b.m-z.m;
    // A/B < C/D;
    if(A/B != C/D) return A/B < C/D;
    return (A%B)*D < (C%D)*B;
}
vector<Line>ch[21];
void INS(Line nw, int IDX){
    while(ch[IDX].size()>=2 && 
        !cmp(ch[IDX][ch[IDX].size()-2], ch[IDX].back(), nw) )
        ch[IDX].pop_back();
    ch[IDX].pb(nw);
}
int QUE(int x, int IDX){ // cari minimum
    int ret = INF;
    int l=0, r=(int)ch[IDX].size()-2, mid=0;
    while(r-l>=5){
        mid = md;
        int le = ch[IDX][mid].getY(x), ri = ch[IDX][mid+1].getY(x);
        chmn(ret, min(le,ri));
        if(le < ri) r = mid-1;
        else l = mid+1;
    }
    for(int i=max(0ll, l-1); i<=min((int)ch[IDX].size(), r+1); i++)
        chmn(ret, ch[IDX][i].getY(x));
    return ret;
}
int idx;
int GETDP(int x){
    int ret = INF;
    for(int i=0; i<=idx; i++) chmn(ret, QUE(x, i));
    return ret;
}

void solve(int nw, int par){
        // chmn(dp[nw], dp[in] -dep[in]*v[nw] + dep[nw]*v[nw]+s[nw]);
    if(nw!=1){
        dp[nw] = GETDP(v[nw]) + dep[nw]*v[nw]+s[nw];
        Line ins; ins.m = -dep[nw]; ins.c = dp[nw];
        // cout << nw << " nw\n";
        INS(ins, idx);
    }
    if(tree[nw].size() == 0) return;
    for(int i=1; i<tree[nw].size(); i++){
        int nx = tree[nw][i];
        ++idx; // ch baru
        solve(nx,nw);
        ch[idx].clear(); // ilangin
        idx--; 
    }
    solve(tree[nw][0], nw);
}
int sub[MAXN];
void dfs(int nw, int par){
    sub[nw] = 1;
    for(auto [nx, wei] : adj[nw]){
        if(nx==par) continue;
        tree[nw].pb(nx);
        dep[nx] = dep[nw]+wei;
        dfs(nx,nw);
        sub[nw] += sub[nx];
    }
}

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("harbingers.in", "r", stdin);
    // freopen("harbingers.out", "w", stdout);
    cin >> n;
    for(int i=1; i<=n-1; i++){
        int u,v,w; cin>>u>>v>>w;
        adj[u].pb({v,w}); adj[v].pb({u,w});
    }
    for(int i=2; i<=n; i++){
        cin>>s[i]>>v[i];
        dp[i] = INF;
    }
    dfs(1,0);
    for(int i=1; i<=n; i++){
        if(tree[i].size() == 0) continue;
        for(int j=1; j<tree[i].size(); j++)
            if(sub[tree[i][0]] < sub[tree[i][j]])
                swap(tree[i][0], tree[i][j]);
    }

    Line ins; ins.m = 0; ins.c = 0; // nw = 0
    INS(ins, 0);
    solve(1,0);
    
    for(int i=2; i<=n; i++) cout << dp[i] << " \n"[i==n];
}

• Subtask 1: 100 / 100