Submission #156305

#	Time	Username	Problem	Language	Result	Execution time	Memory
156305		karma	Harbingers (CEOI09_harbingers)	C++14	60 / 100	252 ms	65540 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 = Cmax): a(a), b(b) {}
    ll GetVal(int x) {return a * v[x - 1] + b;}
};

struct TSegmentMin
{
    Line cur;
    TSegmentMin* left;
    TSegmentMin* right;
    TSegmentMin(Line cur = Line(), TSegmentMin* left = NULL, TSegmentMin* right = NULL): cur(cur), left(left), right(right) {}
};

TSegmentMin* f[N];

TSegmentMin* Update(TSegmentMin* p, int l, int r, int x, int y, Line val)
{
    if(l > y || r < x || l > r) return p;
    int mid = (l + r) >> 1;
    TSegmentMin* res = p ? new TSegmentMin(p -> cur, p -> left, p -> right): new TSegmentMin();
    if(x <= l && r <= y)
    {
        ll lval = val.GetVal(l);
        ll rval = val.GetVal(r);
        ll lcur = res -> cur.GetVal(l);
        ll rcur = res -> cur.GetVal(r);
        if(lcur >= lval && rcur >= rval)
        {
            res -> cur = val;
            return res;
        }
        if(lcur <= lval && rcur <= rval)
        {
            return res;
        }
        ll mval = val.GetVal(mid);
        ll mcur = res -> cur.GetVal(mid);
        if(lcur >= lval && mcur >= mval)
        {
            res -> right = Update(res -> right, mid + 1, r, x, y, res -> cur);
            res -> cur = val;
            return res;
        }
        if(lcur <= lval && mcur <= mval)
        {
            res -> right = Update(res -> right, mid + 1, r, x, y, val);
            return res;
        }
        if(mcur >= mval && rcur >= rval)
        {
            res -> left = Update(res -> left, l, mid, x, y, res -> cur);
            res -> cur = val;
            return res;
        }
        if(mcur <= mval && rcur <= rval)
        {
            res -> left = Update(res -> left, l, mid, x, y, val);
            return res;
        }
    }
    res -> left = Update(res -> left, l, mid, x, y, val);
    res -> right = Update(res -> right, mid + 1, r, x, y, val);
    return res;
}

ll Query(TSegmentMin* p, int l, int r, int x)
{
    if(l > x || r < x || !p) return Cmax;
    ll res = p -> cur.GetVal(x);
    if(l == r) return res;
    res = min(res, Query(p -> left, l, (l + r) >> 1, x));
    res = min(res, Query(p -> right, (l + r) >> 1 | 1, r,  x));
    return res;
}

int in[N], n, out[N], Time = 0;
ll d[N], g[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;
       g[u] = Query(f[u], 1, int(v.size()), vantoc[u]) + d[u] * v[vantoc[u] - 1] + chuanbi[u];
    }
    for(pii p: a[u]) {
        if(par == p.fi) continue;
        f[p.fi] = Update(f[u], 1, int(v.size()), 1, int(v.size()), Line(-d[u], g[u]));
        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());
    GetAns(1, 1);
    for(int i = 2; i <= n; ++i) cout << g[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:157: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:158: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: 60 / 100