Submission #156301

#	Time	Username	Problem	Language	Result	Execution time	Memory
156301		karma	Harbingers (CEOI09_harbingers)	C++14	40 / 100	325 ms	35268 KiB

harbingers

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define FileName      "test"
#define ll            long long
#define ld            long double
#define pb            emplace_back
#define fi            first
#define se            second

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ord_set;
typedef pair<int, int> pii;
typedef pair<ll, int> plli;
const int N = int(2e5) + 2;
const int oo = int(1e9) + 7;
const ll Cmax = 1ll * oo * oo;

vector<ll> v;
struct line
{
    ll a, b;
    line (ll a = 0, ll b = 0): a(a), b(b) {}
    ll GetVal(int id) {return a * v[id - 1] + b;}
};

struct TSegment
{
    int l, r, mid;
    line cur;
    TSegment* left;
    TSegment* right;

    TSegment (int l = 0, int r = 0): l(l), r(r)
    {
        mid = (l + r) >> 1;
        cur = line();
        if(l == r)
        {
            left = right = NULL;
            return;
        }
        left = new TSegment(l, mid);
        right = new TSegment(mid + 1, r);
    }

    void Update(int x, int y, line val)
    {
        if(l > y || r < x) return;
        if(x <= l && r <= y)
        {
            ll lcur = cur.GetVal(l);
            ll rcur = cur.GetVal(r);
            ll lval = val.GetVal(l);
            ll rval = val.GetVal(r);
            if(lcur >= lval && rcur >= rval) {cur = val; return;}
            if(lcur <= lval && rcur <= rval) return;
            ll mval = val.GetVal(mid);
            ll mcur = cur.GetVal(mid);
            if(lcur >= lval && mcur >= mval)
            {
                right -> Update(x, y, cur);
                cur = val;
                return;
            }
            if(lcur <= lval && mcur <= mval)
            {
                right -> Update(x, y, val);
                return;
            }
            if(mcur >= mval && rcur >= rval)
            {
                left -> Update(x, y, cur);
                cur = val;
                return;
            }
            if(mcur <= mval && rcur <= rval)
            {
                left -> Update(x, y, val);
                return;
            }
        }
        left -> Update(x, y, val);
        right -> Update(x, y, val);
    }

    ll Query(int x)
    {
        if(l > x || r < x) return Cmax;
        ll res = cur.GetVal(x);
        if(l == r) return res;
        res = min(res, left -> Query(x));
        res = min(res, right -> Query(x));
        return res;
    }
} Min;

int in[N], n, out[N], Time = 0;
ll d[N], f[N], vantoc[N], chuanbi[N];
vector<pii> a[N];

void DFS(int u, int par) {
    in[u] = ++Time;
    for(pii p: a[u]) {
       if(par == p.fi) continue;
       d[p.fi] = d[u] + p.se;
       DFS(p.fi, u);
    }
    sort(a[u].begin(), a[u].end(), [](const pii& x, const pii& y) {
           return d[x.fi] < d[y.fi];
         });
    out[u] = Time;
}

void GetAns(int u, int par) {
    ///f[v] = -d[u] * vantoc[v] + f[u] + chuanbi[v] + d[v] * vantoc[v];
    if(u != 1) {
       vantoc[u] = lower_bound(v.begin(), v.end(), vantoc[u]) - v.begin() + 1;
       f[u] = Min.Query(vantoc[u]) + d[u] * v[vantoc[u] - 1] + chuanbi[u];
       //cout << Min.Query(vantoc[u]) << ' ';
       //cout << u << ' ' << -d[u] << ' ' << f[u] << '\n';
       Min.Update(1, int(v.size()), line(-d[u], f[u]));
    }
    for(pii p: a[u]) {
        if(par == p.fi) continue;
        GetAns(p.fi, u);
    }
}

void Enter() {
    cin >> n;
    for(int i = 1; i < n; ++i) {
        int u, v, l;
        cin >> u >> v >> l;
        a[u].pb(v, l), a[v].pb(u, l);
    }
    v.clear();
    for(int i = 2; i <= n; ++i) {
        cin >> chuanbi[i] >> vantoc[i];
        v.pb(vantoc[i]);
    }
    DFS(1, 1);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    Min = TSegment(1, int(v.size()) + 1);
    GetAns(1, 1);
    for(int i = 2; i <= n; ++i) cout << f[i] << ' ';
}

void Solve() {

}

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

    Enter(), Solve();

    return 0;
}

Compilation message (stderr)

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

• Subtask 1: 40 / 100