Submission #970705

#	Time	Username	Problem	Language	Result	Execution time	Memory
970705		Pentagon	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1066 ms	32304 KiB

harbingers

#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt")
#include"bits/stdc++.h"
using namespace std;
#define nl '\n'
#define sp ' '
#define dbg(i) cerr<<#i<<sp<<i<<endl
#define dbgs(...) fprintf(stderr, __VA_ARGS__)
#define all(v) (v).begin(), (v).end()
using ll = long long;
// dont use below with atcoder header or tight constrain
// #define int ll
using pii = pair<int,int>;
int cur_tc;
std::mt19937_64 gen(time(NULL));
ll randint(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }

/*Solution
https://acmicpc.net/problem/3319
1. 문제부터 정확히 읽는다.
2. 사고 전환을 빠르게 한다.
3. 한줄 한줄 정신 차리고 작성한다.

*/
constexpr int N = 1e5 + 7, inf = (int)1e9 + 7, mod = (int)1e9 + 7, LOOP = 3e5;
constexpr ll linf = (ll)4e18 + 7;

/*
rollback Line container for dynamic CHT that can be Rollbacked. (Persistent)
y = kx + m
qry: gives minimum value for given x, Lower hull
find bool operator< (const Line& o) to change minimum / maximum properties.
for minimum: k > o.k, x->m < y->m
for maximum: k < o.k, x->m > y->m
for doubles, change all (ll -> double), (inf -> 1/.0), (div(a,b) = a/b)
reference: https://github.com/kth-competitive-programming/kactl/blob/main/content/data-structures/LineContainer.h
*/
using pll = pair<ll,ll>;
struct Line{
    mutable ll k, m, p;
    bool operator<(const Line& o) const{return k!=o.k?k>o.k:m<o.m;} // chg here
    bool operator<(ll x) const {return p < x;}
};
struct LineContainer : multiset<Line, less<>> {
    static const ll inf = LLONG_MAX;
    ll div(ll a, ll b){ // floored division
        return a / b - ((a ^ b) < 0 && a % b);
    }
    bool apply(iterator x, iterator y){
        assert(next(x) == y);
        if(y == end()){
            x->p = inf;
            return false;
        }
        if(x->k == y->k) x->p = (*x<*y?inf:-inf);
        else x->p = div(y->m - x->m, x->k - y->k);
        return x->p >= y->p;
    }
    vector<int> info; vector<pll> S;
    bool add(ll k, ll m){
        Line t = Line{k, m, -inf}; auto z = lower_bound(t);
        if(z!=end() && k == z->k){info.push_back(0); return false;}
        if(z!=begin()) --z;
        z = insert(z, t); auto y = z++, x = y; 
        auto it = x; vector<pll> v;
        while(apply(y, z)) v.emplace_back(z->k,z->m), z = erase(z);
        if(x != begin() && apply(--x, y)){
            apply(x, y = erase(y));
            assert(v.size() == 0); info.push_back(0);
            return false;
        }
        reverse(v.begin(), v.end());
        while((y=x) != begin() && (--x)->p >= y->p) v.emplace_back(y->k,y->m), apply(x, erase(y));
        assert(it != end()); v.emplace_back(it->k,it->m);
        S.insert(S.end(), v.begin(), v.end()); info.push_back(v.size());
        return true;
    }
    void print_it(iterator it){dbgs("%dth %lld %lld %lld\n",(int)distance(begin(),it), it->k, it->m, it->p);}
    void print(){
        dbg(size());
        for(auto it = begin(); it != end(); it++)
            print_it(it);
    }
    void rollback(){
        // print();
        auto c = info.back(); info.pop_back();
        if(c == 0) return;
        auto l = S.back(); S.pop_back(); --c;
        auto it = lower_bound(Line{l.first,l.second,-inf}); 
        assert(it != end() && it->k == l.first && it->m == l.second);
        it = erase(it);
        if(c==0){
            if(size() > 0 && it != begin()) apply(prev(it), it);
            return;
        }
        auto z = it;
        bool flag = true;
        if(it != begin()) --it;
        else flag = false;
        auto x = it, y = it; 
        for(int i=1;i<=c;i++){
            auto[k,m] = S[S.size()-i];
            y = insert(x, Line{k,m,-inf});
            if(i>1||flag) apply(x, y);
            x = y;
        }
        apply(y, z);
        S.resize(S.size()-c);
    }
    ll qry(ll x){
        assert(!empty());
        auto l = lower_bound(x); assert(l != end());
        return l->k * x + l->m;
    }
};

LineContainer lc;
vector<pii> g[N];
int par[N], S[N], V[N];
ll dep[N], dp[N], h[N];
void dfs(int x){
    if(x != 1) dp[x] = S[x] + dep[x] * V[x] + lc.qry(V[x]);
    lc.add(-dep[x], dp[x]);
    for(auto [nx, d]:g[x]) if(nx != par[x]){
        dep[nx] = dep[x] + d; par[nx] = x; h[nx] = h[x] + 1;
        dfs(nx);
    }
    assert(lc.info.size() == h[x] + 1);
    lc.rollback();
}
void solve(){
    int n; cin>>n;
    for(int i=0;i<n-1;i++){
        int a, b, d; cin>>a>>b>>d;
        g[a].push_back(pii(b,d)); g[b].push_back(pii(a,d));
    }
    for(int i=2;i<=n;i++) cin>>S[i]>>V[i];
    lc.S.reserve(n); lc.info.reserve(n); 
    dfs(1);
    for(int i=2;i<=n;i++) cout<<dp[i]<<sp;
    cout<<nl;
}

signed main(){
    cin.tie(0)->sync_with_stdio(0);
    // cout<<fixed<<setprecision(15);
    int tc = 1;
    // cin >> tc;
    for(cur_tc=1;cur_tc<=tc;++cur_tc) solve();
    return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from harbingers.cpp:4:
harbingers.cpp: In function 'void dfs(int)':
harbingers.cpp:129:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
  129 |     assert(lc.info.size() == h[x] + 1);
      |            ~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 70 / 100