Submission #1250816

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250816		nanaseyuzuki	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	32668 KiB

harbingers

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
/*
    --> Author: Kazuki_Hoshino__8703 <--
    I love Nanasaki Ai ☆*: .。. o(≒＿≒)o .。.:☆
*/
#define fi first
#define se second
#define pii pair<int, ll>
#define ll long long
using namespace std;

const int mn = 1e5 + 5, bm = (1 << 15) + 1, mod = 1532023;
const double inf = 1e18;

int n, h[mn];
ll s[mn], v[mn];
vector <pii> a[mn];
double d[mn], dp[mn];

struct line{ double a, b; };

vector <line> reina;
vector <double> pts;

double center(line x, line y){
    return (double)(x.b - y.b) / (double)(y.a - x.a);
}

struct mov{
    line x;
    double pts;
    int add;
};

vector <mov> moves;

void add(line x){
    while(reina.size() && reina.back().a == x.a && reina.back().b > x.b){
        moves.push_back({reina.back(), pts.back(), -1});
        reina.pop_back();
        pts.pop_back();
    }
    while(reina.size() >= 2 && center(x, reina.back()) <= pts.back()){;
        moves.push_back({reina.back(), pts.back(), -1});
        reina.pop_back();
        pts.pop_back();
    }
    if(reina.size()) pts.push_back(center(x, reina.back()));
    else pts.push_back(-inf);
    reina.push_back(x);
    moves.push_back({x, pts.back(), 1});
}

void rollback(int snap){
    while((int)moves.size() > snap){
        int add = moves.back().add;
        line kumiko = moves.back().x;
        double y = moves.back().pts;
        moves.pop_back();
        if(add == 1){
            reina.pop_back();
            pts.pop_back();
        }
        else{
            reina.push_back(kumiko);
            pts.push_back(y);
        }
    }
}

ll val(ll x){
    int id = upper_bound(pts.begin(), pts.end(), (double)x) - pts.begin() - 1;
    return reina[id].a * x + reina[id].b;
}

void dfs(int u, int p){
    int snapshot = moves.size();
    line kumiko = {-d[u], dp[u]};
    add(kumiko);
    for(auto i : a[u]){
        int vv; ll c; tie(vv, c) = i;
        if(vv == p) continue;
        h[vv] = h[u] + 1;
        d[vv] = d[u] + c;
        dp[vv] = val(v[vv]) + v[vv] * d[vv] + s[vv];
        dfs(vv, u);
    }
    rollback(snapshot);
}

void solve(){
    cin >> n;
    for(int i = 1; i < n; i++){
        int u, vv; ll c; cin >> u >> vv >> c;
        a[u].push_back({vv, c});
        a[vv].push_back({u, c});
    }
    for(int i = 2; i <= n; i++) cin >> s[i] >> v[i];
    dfs(1, 0);
    for(int i = 2; i <= n; i++) cout << (long long)dp[i] << ' ';
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}

Compilation message (stderr)

harbingers.cpp:22:39: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
   22 | #pragma GCC optimize("-fwhole-program")
      |                                       ^
harbingers.cpp:29:41: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
   29 | #pragma GCC optimize("-fstrict-overflow")
      |                                         ^
harbingers.cpp:31:41: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
   31 | #pragma GCC optimize("-fcse-skip-blocks")
      |                                         ^
harbingers.cpp:45:51: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
   45 | #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                   ^
harbingers.cpp:72:29: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   72 | double center(line x, line y){
      |                             ^
harbingers.cpp:72:29: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:72:29: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:72:29: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
   84 | void add(line x){
      |                ^
harbingers.cpp:84:16: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:84:16: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  101 | void rollback(int snap){
      |                       ^
harbingers.cpp:101:23: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:101:23: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  118 | ll val(ll x){
      |            ^
harbingers.cpp:118:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:118:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  123 | void dfs(int u, int p){
      |                      ^
harbingers.cpp:123:22: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:123:22: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  138 | void solve(){
      |            ^
harbingers.cpp:138:12: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:138:12: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  150 | signed main(){
      |             ^
harbingers.cpp:150:13: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
harbingers.cpp:150:13: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• Subtask 1: 70 / 100