Submission #1245579

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245579		enxiayy	Harbingers (CEOI09_harbingers)	C++20	10 / 100	1096 ms	21620 KiB

harbingers

#include <bits/stdc++.h>
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define compact(v) v.erase(unique(all(v)), v.end())
#define dbg(v) "[" #v " = " << (v) << "]"
#define el "\n"

using namespace std;
typedef long long ll;
typedef long double ld;

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long randRange(long long l, long long r){ return uniform_int_distribution<long long>(l,r)(rng); }

const int N = 2e5 + 5;

int n;
vector < pair<int, ll> > adj[N];
int tin[N], idx[N], timer = 0;
ll dist[N] ,v[N], c[N], dp[N];

void dfs(int u, int par) {
    tin[u] = ++timer;
    idx[tin[u]] = u;
    for(pair<int, ll> s : adj[u]) {
        int v = s.first;
        ll w = s.second;
        if (v == par) continue; 
        dist[v] = dist[u] + w;
        dfs(v, u);
    }
}

struct Line {
    ll a, b;
    Line (ll a = 0, ll b = 0) : a(a), b(b) {}

    ll f(ll x) {
        return a * x + b;
    }

    ld intersect(Line Other) {
        return 1.0 * (Other. b - b) / (a - Other.a);
    }

    // decreasing slope
    friend bool bad(Line d1, Line d2, Line d3) {
        return d1.intersect(d3) <= d1.intersect(d2);
    }
};

struct CHT {
    vector <Line> hull;

    CHT() {
        hull.clear();
    }

    void add(Line d) {
        while((int)hull.size() >= 2) {
            if (bad(hull[(int)hull.size() - 2], hull.back(), d))
                hull.pop_back();
            else break;
        } 
        hull.eb(d);
    }

    ll query(ll x) {
        int l = 0;
        int r = (int)hull.size() - 1;
        ll ans = LLONG_MAX;
        while(l <= r) {
            int mid = (l + r) >> 1;
            ll cur = hull[mid].f(x);
            ans = min(ans, cur);
            if (mid > 0 && hull[mid - 1].f(x) < cur) r = mid - 1;
            else if (mid < (int)hull.size() - 1 && hull[mid + 1].f(x) < cur) l = mid + 1;
            else break;
        }
        return ans;
    } 
};

void dfsAns(int i, int par, vector <int> &pre) {
    dp[i] = dist[i] * v[i] + c[i];
    for(int j : pre) {
        dp[i] = min(dp[i], -dist[j] * v[i] + dp[j] + v[i] * dist[i] + c[i]); 
    }
    for(pair<int, ll> s : adj[i]) {
        int v;
        ll w;
        tie(v, w) = s;
        if (v == par) continue;
        pre.eb(i);
        dfsAns(v, i, pre);
    }
}

void solve() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        adj[u].eb(v, w);
        adj[v].eb(u, w);
    }

    for(int i = 2; i <= n; ++i) {
        cin >> c[i] >> v[i];
    }

    memset(dp, 0x3f, sizeof(dp));

    dfs(1, -1);
    vector <int> pre;
    pre.clear();
    dfsAns(1, -1, pre);
    for(int i = 2; i <= n; ++i) 
        cout << dp[i] << " ";
    // CHT cht = CHT();

}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    #define task "task" 
    if(fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    solve();

    return 0;
}

/*

*/

Compilation message (stderr)

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

• Subtask 1: 10 / 100