Submission #970698

#	Time	Username	Problem	Language	Result	Execution time	Memory
970698		Pentagon	Harbingers (CEOI09_harbingers)	C++17	70 / 100	1067 ms	32300 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
*/
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){
        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<Line> S;
    bool add(ll k, ll m){
        auto z = insert({k, m, -inf}), y = z++, x = y; 
        auto it = x; vector<Line> v;
        while(apply(y, z)) v.push_back(*z), 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.push_back(*y), apply(x, erase(y));
        assert(it != end()); v.push_back(*it);
        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();
        assert(!info.empty());
        auto c = info.back(); info.pop_back();
        if(c == 0) return;
        assert(c <= (int)S.size());
        auto l = S.back(); S.pop_back(); --c;
        auto it = lower_bound(l); 
        assert(it != end() && it->k == l.k && it->m == l.m);
        it = erase(it);
        if(c==0){
            if(it != begin()) apply(prev(it), it);
            return;
        }
        auto tmp = it;
        if(it != begin()) --it;
        auto y = it; 
        for(int i=1;i<=c;i++) y = insert(y, S[S.size()-i]);
        S.resize(S.size()-c);
        if(it == next(y)) it = begin();
        assert(next(y) == tmp);
        for(auto x = y++; ;--x, --y){// note that x's initial iterator is valid
            apply(x, y);
            if(x == it) break;
        }
    }
    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:124: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]
  124 |     assert(lc.info.size() == h[x] + 1);
      |            ~~~~~~~~~~~~~~~^~~~~~~~~~~

• Subtask 1: 70 / 100