Submission #1128596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128596		cbnhtmanh	Harbingers (CEOI09_harbingers)	C++20	70 / 100	1096 ms	27972 KiB

harbingers

#include <bits/stdc++.h>
#define fi(i, a, b) for( int i = a; i <= b; i++ )
#define fid(i, a, b) for( int i = a; i >= b; i-- )
#define getbit(x, i) ((x>>i)&1)
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define st first
#define nd second
#define mp make_pair
#define HTManh ""
#define maxn 100009
#define endl '\n'
using namespace std;

int n;
vector<pii> a[100009];
ll v[100009], s[100009];

struct cht
{
    vector<pll> line;
    vector<long double> diem;

    stack<pair<pll, long double>> s;

    long double f(pll dt1, pll dt2)
    {
        return (double)(dt2.nd - dt1.nd)/(dt1.st - dt2.st);
    }

    void add(pll x)
    {
        while(line.size() >= 2)
        {
            pll dtg = line[(int)line.size()-2];
            if (f(dtg, x) < f(line.back(), x)) break;
            s.push({line.back(), diem.back()});
            diem.pop_back();
            line.pop_back();
        }
        if (line.empty())
        {
            diem.pb(-1e18);
            line.pb(x);
        }
        else
        {
            diem.pb(f(line.back(), x));
            line.pb(x);
        }
        s.push({{0, 0}, -1e18-1});
    }

    ll get(ll x)
    {
        if (diem.empty()) return 0;
        int vt = lower_bound(diem.begin(), diem.end(), x) - diem.begin();
        return line[vt-1].st*x+line[vt-1].nd;
    }

    void rollback(int t)
    {
        while (s.size() > t)
        {
            pll dg = s.top().st;
            long double pt = s.top().nd;
            s.pop();

            if (pt == -1e18-1)
            {
                diem.pop_back();
                line.pop_back();
            }
            else
            {
                diem.pb(pt);
                line.pb(dg);
            }
        }
    }
} mmb;

ll dp[100009];

void dfs(int u, int pre = 0, ll dis = 0)
{
    dp[u] = mmb.get(v[u]) + dis*v[u] + s[u];
    //cout << u << " " << dp[u] << endl;
    int tg = mmb.s.size();
    mmb.add({-dis, dp[u]});
    for(pii tg: a[u])
    {
        int v = tg.st, kc = tg.nd;
        if (v == pre) continue;
        dfs(v,u,dis+kc);
    }
    mmb.rollback(tg);
}

mt19937_64 rng(time(0));

ll rnd(ll d, ll c)
{
    return uniform_int_distribution<ll>(d, c)(rng);
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL); cout.tie(NULL);
	if (fopen(HTManh".inp", "r"))
    {
        freopen(HTManh".inp", "r", stdin);
        freopen(HTManh".out", "w", stdout);
    }

    cin >> n;
    fi(i,1,n-1)
    {
        int x,y,z;
        cin >> x >> y >> z;
        a[x].pb({y,z});
        a[y].pb({x,z});
    }
    fi(i,2,n) cin >> s[i] >> v[i];
    dfs(1);
    fi(i,2,n) cout << dp[i] << " ";
    cout << endl;

//    n = 100000;
//    cout << n << endl;
//    fi(i,2,n)
//    {
//        cout << i-1 << " " << i << ' ' << rnd(9e3,1e4) << endl;
//    }
//    fi(i,2,n)
//    {
//        cout << rnd(9e8,1e9) << " " << rnd(9e8,1e9) << endl;
//    }
}

Compilation message (stderr)

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

• Subtask 1: 70 / 100