Submission #1123422

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123422		LTTrungCHL	Harbingers (CEOI09_harbingers)	C++20	60 / 100	90 ms	20548 KiB

harbingers

///***LTT***///
/// ->NHAT QUOC GIA<- ///
#include<bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("popcnt")
#define int long long
#define endl "\n"
#define F first
#define S second
#define pb push_back
using namespace std;
//vector <int> lg2;
//void LOG_ARR(int n){
//    lg2.resize(n + 3);
//    for (int i = 1;i <= n;++i){
//        lg2[i] = __lg(i);
//    }
//}
const long long oo = 1e9+7;
const int N = 2 * 1e5 + 10;
int n;
typedef long long ll;
vector <pair <int, long long>> adj[N];
long long dp[N];
long long h[N];
long long s[N], v[N];
namespace sub1{
    int parent[N];
    void dfs(int u, int p){
        if (u - 1){
            int tmp = parent[u];
            dp[u] = 1ll * h[u] * v[u] + s[u];
            while (tmp - 1){
                dp[u] = min(dp[u], dp[tmp] + s[u] + v[u] * (h[u] - h[tmp]));
                tmp = parent[tmp];
            }
        }
        for (int i = 0;i < adj[u].size();++i){
            int v = adj[u][i].F;
            int w = adj[u][i].S;
            if (v == p) continue;
            parent[v] = u;
            h[v] = h[u] + w;
            dfs(v, u);
        }
    }
    void solve(){
        dfs(1, 0);
        for (int i = 2;i <= n;++i){
            cout << dp[i] <<" ";
        }
        return;
    }
};
bool dsub2(){
    for (int i = 1;i <= n;++i){
        if (adj[i].size() > 2) return false;
    }
    return true;
}
namespace sub2{
    struct Line{
        mutable long long k, m, p;
        bool operator<(const Line& o) const {return k > o.k;}
        bool operator<(long long x) const {return p < x;}
    };
    struct CHT : multiset <Line, less<>>{
        /// double : INF = 1/.0 div(a,b) = a/b;
        static const long long inf = LLONG_MAX;
        long long div(long long a, long long b){
            return a/b;
        }
        long long bad(iterator x,iterator y){
            if (y == end()) return x->p = inf, 0;
            if (x->k == y->k) x->p = x->m < y->m ? inf : - inf;
            else x->p = div(y->m - x->m, x->k - y->k);
            return x->p >= y-> p;
        }
        void add(long long k, long long m){
            auto z = insert({k, m, 0}), y = z++, x = y;
            while(bad(y,z)) z = erase(z);
            if (x != begin() and bad(--x,y)) bad(x, y = erase(y));
            while ( (y = x) != begin() and (--x)->p >= y->p ){
                bad(x, erase(y));
            }
        }
        long long query(long long x){
            assert(!empty());
            Line l = *lower_bound(x);
            return l.k * x + l.m;
        }
    };
    CHT a[2];
    void dfs(int u, int p, int id, bool qr){
        dp[u] = 1ll * h[u] * v[u] + s[u];
        if (qr)
            dp[u] = min(dp[u], a[id].query(v[u]) + s[u] + v[u] * h[u]);
        a[id].add(-h[u], dp[u]);
        for (int i = 0;i < adj[u].size();++i){
            int v = adj[u][i].F;
            int w = adj[u][i].S;
            if (v == p) continue;
            h[v] = h[u] + w;
            dfs(v, u, id,1);
        }
    }
    void solve(){
        for (int i = 0;i < adj[1].size();++i){
            int v = adj[1][i].F;
            int w = adj[1][i].S;
            h[v] = w;
            dfs(v, 1, i, 0);
        }
        for (int i = 2;i <= n;++i){
            cout << dp[i] <<" ";
        }
    }
};
void solve(){
    cin >> n;
    for (int i = 1;i < n;++i){
        int u, v, d;
        cin >> u >> v >> d;
        adj[u].pb({v, d});
        adj[v].pb({u, d});
    }
    for (int i = 2;i <= n;++i){
        cin >> s[i] >> v[i];
    }
    if (n <= 5000){
        sub1::solve();
        return;
    }
    if (dsub2()){
        sub2::solve();
        return;
    }
    return;
}
signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL);
    cout.tie(NULL);
    if (fopen("harb.inp", "r")){
        freopen("harb.inp", "r", stdin);
        freopen("harb.out", "w", stdout);
    }
//    int t;
//    cin >> t;
//    while(t--){
    solve();
//    }
    return 0;
}
//////

Compilation message (stderr)

harbingers.cpp: In function 'int main()':
harbingers.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen("harb.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen("harb.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 60 / 100