Submission #764407

#	Time	Username	Problem	Language	Result	Execution time	Memory
764407		shjeong	Harbingers (CEOI09_harbingers)	C++14	30 / 100	118 ms	65536 KiB

harbingers

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
/******************************************************************************
 * dp[i] := i에서 1까지 가는데 걸리는 최솟값
 * i에서 j까지 가는데에 전령 i를 이용해야 함. 이후는 그냥 dp[j]
 * dp[i] = min(j is element of i's ancestor) (dp[j] + (dis(i)-dis(j)) * Vi)+Si
 * =min(-dis(j)*Vi +dp[j]) + Si + dis(i)*Vi
 * dfs상에서 자기 정점이 끝날 때 li-chao에서 직선 제거
 * 구현할 때는 li-chao에서 i 정점의 직선을 넣을 때, 변화한 위치를 벡터에 저장
 * vector<pair<node,node>>changed[i] : i.first가 i.second로 변화함
 *
*******************************************************************************/
using namespace std;
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
typedef long long ll;
const ll inf1 = 2e9, inf2 = 2e18;
struct Line{
    ll a,b;
    ll f(ll x){return a*x+b;}
};
Line max(Line a, Line b, ll x){
    return a.f(x) >= b.f(x) ? a : b;
}
Line min(Line a, Line b, ll x){
    return a.f(x) <= b.f(x) ? a : b;
}
struct Node{
    int l,r;
    ll s,e;
    Line line;
};
struct asdf{
    int x;
    Node before;
    int num;
};
struct seg{
    vector<Node> tree;
    void init(ll s, ll e){
        tree.push_back({-1,-1,s,e,{0,inf2}});
    }
    deque<asdf> changed;
    inline void upd(ll node, Line k, int num){
        auto push = [&](int x, Node a, int c) -> void {
            changed.push_back({x,a,c});
        };
        ll s = tree[node].s, e = tree[node].e;
        Line low = min(tree[node].line, k, s), high = max(tree[node].line, k, s);
        if(low.f(e) <= high.f(e)){
            auto cur = tree[node];
            tree[node].line = low;
            push(num, cur, node);
            return;
        }
        ll mid = s+e>>1;
        if(low.f(mid) < high.f(mid)){
            auto cur = tree[node];
            tree[node].line = low;
            if(tree[node].r == -1){
                push(num, {-2,-2,-2,-2,{-2,-2}}, tree.size());
                tree[node].r = tree.size();
                tree.push_back({-1,-1,mid+1,e,{0,inf2}});
            }
            push(num, cur, node);
            upd(tree[node].r, high, num);
        }
        else{
            auto cur = tree[node];
            tree[node].line = high;
            if(tree[node].l == -1){
                push(num, {-2,-2,-2,-2,{-2,-2}}, tree.size());
                tree[node].l = tree.size();
                tree.push_back({-1,-1,s,mid,{0,inf2}});
            }
            push(num, cur, node);
            upd(tree[node].l, low, num);
        }
    }
    inline ll query(ll node, ll x){
        if(node==-1)return inf2;
        ll s = tree[node].s, e = tree[node].e;
        ll mid = s+e>>1;
        if(x<=mid)return min(tree[node].line.f(x), query(tree[node].l, x));
        return min(tree[node].line.f(x), query(tree[node].r, x));
    }
    inline void rollback(ll x){
        while(changed.size() and changed.back().x == x){
            auto [x,a,i] = changed.back();
            changed.pop_back();
            if(a.l==-2)tree.pop_back();
            else tree[i] = a;
        }
    }
} seg;
ll n;
bool visited[101010];
vector<pair<int,ll>> adj[101010];
ll dp[101010];
ll depth[101010];
ll s[101010], v[101010];
void dfs(ll x, ll y){
    visited[x]=1;
    depth[x]=y;
    if(x!=1)dp[x] = seg.query(0, v[x])+(ll)s[x]+depth[x]*v[x];
    seg.upd(0, {-depth[x], dp[x]}, x);
    for(auto [next,w] : adj[x]){
        if(visited[next])continue;
        dfs(next, y+w);
    }
    seg.rollback(x);
}
int main(){
    fast;
    cin>>n;
    seg.init(-inf1, inf1);
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b,c; cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i = 2 ; i <= n ; i++){
        cin>>s[i]>>v[i];
    }
    dfs(1,0);
    for(int i = 2 ; i <= n ; i++)cout<<dp[i]<<" ";
}

Compilation message (stderr)

harbingers.cpp: In member function 'void seg::upd(ll, Line, int)':
harbingers.cpp:72:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |         ll mid = s+e>>1;
      |                  ~^~
harbingers.cpp: In member function 'll seg::query(ll, ll)':
harbingers.cpp:99:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |         ll mid = s+e>>1;
      |                  ~^~
harbingers.cpp: In member function 'void seg::rollback(ll)':
harbingers.cpp:105:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  105 |             auto [x,a,i] = changed.back();
      |                  ^
harbingers.cpp: In function 'void dfs(ll, ll)':
harbingers.cpp:123:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     for(auto [next,w] : adj[x]){
      |              ^

• Subtask 1: 30 / 100