oj.uz

Submission #131537

# Submission time Handle Problem Language Result Execution time Memory
131537 2019-07-17T08:57:52 Z lyc Harbingers (CEOI09_harbingers) C++14
70 / 100
 1000 ms 31076 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 1e5+5;

int N;
vector<ii> al[MAXN];
int S[MAXN], V[MAXN];
int p[MAXN];
int d[MAXN];
ll r[MAXN];

struct Line { int m; ll b; };
const Line END = {(int)-2e9, (ll)-3e18};
struct Op { Line o, n; };
struct Hull {
    vector<Line> v; 
    vector<Op> h;

    int add(Line l) {
        //cout << "ADD " << l.m << " " << l.b << endl;
        int idx = SZ(h);
        int s; while ((s = SZ(v)) > 2) {
            if (((ll)l.b-v[s-1].b)*((ll)v[s-2].m-v[s-1].m) <= (((ll)v[s-1].b-v[s-2].b)*((ll)v[s-1].m-l.m)))
                h.emplace_back((Op){ v[s-1], END }), v.pop_back();
            else break;
        }
        h.emplace_back((Op){ END, l });
        v.emplace_back(l);
        return idx;
    }

    ll query(int x) {
        //cout << "QUERY " << SZ(v) << ": ";
        //for (auto l : v) cout << "(" << l.m << "," << l.b << ") ";
        //cout << endl;
        int lo = 0, hi = SZ(v)-1;
        while (lo < hi) {
            int mid = (lo+hi)/2;
            bool ok = ((ll)x*((ll)v[mid].m-v[mid+1].m) <= (ll)v[mid+1].b-v[mid].b);
            if (ok) hi = mid;
            else lo = mid+1;
        }
        return (ll)v[hi].m*x + v[hi].b;
    }

    void undo(int idx) {
        //cout << "UNDO " << endl;
        while (SZ(h) > idx) {
            Op cur = h.back();
            if (cur.o.m == END.m && cur.o.b == END.b) { v.pop_back(); }//cout << "\t\tPOP\n"; }
            else { v.push_back(cur.o); }//cout << "\t\tPUSH " << cur.o.m << " " << cur.o.b << '\n'; }
            h.pop_back();
        }
    }
} ch;

void dfs(int u) {
    r[u] = (ll)S[u] + (ll)V[u]*d[u];
    //cout << u << " " << p[u] << endl;
    //for (int v = p[u]; v != 0; v = p[v]) r[u] = min(r[u], (ll)S[u] + (ll)V[u]*(d[u]-d[v]) + r[v]);
    if (u > 1) r[u] = min(r[u], ch.query(V[u]) + (ll)S[u] + (ll)V[u]*d[u]);
    int idx = ch.add({ -d[u], r[u] });
    for (auto v : al[u]) if (v.fi != p[u]) {
        d[v.fi] = d[u] + v.sc;
        p[v.fi] = u;
        dfs(v.fi);
    }
    ch.undo( idx );
}

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    FOR(i,1,N-1){
        int u, v, d; cin >> u >> v >> d;
        al[u].emplace_back(v, d);
        al[v].emplace_back(u, d);
    }

    FOR(i,2,N){ cin >> S[i] >> V[i]; }
    dfs(1);

    FOR(i,2,N) cout << r[i] << (i == N ? '\n' : ' ');
}

Subtask #1
70.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2680 KB Output is correct
2 Correct 7 ms 3704 KB Output is correct
3 Correct 71 ms 14692 KB Output is correct
4 Correct 91 ms 20096 KB Output is correct
5 Correct 129 ms 25728 KB Output is correct
6 Correct 162 ms 31076 KB Output is correct
7 Correct 100 ms 13416 KB Output is correct
8 Execution timed out 1076 ms 20328 KB Time limit exceeded
9 Execution timed out 1078 ms 14192 KB Time limit exceeded
10 Execution timed out 1070 ms 22376 KB Time limit exceeded