Submission #167115

#	Time	Username	Problem	Language	Result	Execution time	Memory
167115		HellAngel	Harbingers (CEOI09_harbingers)	C++14	0 / 100	1077 ms	29472 KiB

harbingers

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int maxn = 2e5 + 7;
int n, m, x[maxn], y[maxn], cnt, v[maxn], d[maxn], st[maxn], ahihi;

int a[maxn], dp[maxn];
vector<pair<int, int>> vt[maxn];

struct Line
{
    int id;
    int a, b;
    Line(){}
    Line(int id, int a, int b): id(id), a(a), b(b) {};
};

int Get(const Line & u, const int &v)
{
    return u.a * v + u.b;
}

bool Ok(const Line &u, const Line &v, const Line &w)
{
    return (u.b - v.b) * (w.a - u.a) < (u.b - w.b) * (v.a - u.a);
}
vector<pair<int, Line>> deleted;
vector<Line> hull;

void Insert(int u, Line x)
{
    while(hull.size() > 1 && !Ok(hull[hull.size() - 2], hull[hull.size() - 1], x))
    {
        ahihi++;
        deleted.push_back({u, hull.back()});
        hull.pop_back();
    }
    hull.push_back(x);
}

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

void DFS(int u, int p)
{
    st[u] = ++cnt;
    if(u != 1) dp[u] = a[u] + d[u] * v[u] + Find(v[u]);
    Insert(cnt, Line(cnt, -d[u], dp[u]));
    for(auto i: vt[u])
    {
        int v = i.first;
        int w = i.second;
        if(v != p)
        {
            d[v] = d[u] + w;
            DFS(v, u);
            while(hull.size() && hull.back().id > st[u])
            {
                ahihi++;
                hull.pop_back();
            }
            int cac = -1;
            for(int j = (int)deleted.size() - 1; j >= 0; j--)
            {
                if(deleted[j].first == st[v])
                {
                    ahihi++;
                    hull.push_back(deleted[j].second);
                    deleted.pop_back();
                }
            }
        }
    }
    hull.pop_back();
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        vt[u].push_back({v, w});
        vt[v].push_back({u, w});
    }
    for(int i = 2; i <= n; i++) cin >> a[i] >> v[i];
    DFS(1, 1);
    for(int i = 2; i <= n; i++) cout << dp[i] << ' ';
    cerr << ahihi;
}

Compilation message (stderr)

harbingers.cpp: In function 'long long int Find(long long int)':
harbingers.cpp:48:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r >> 1;
                   ~~^~~
harbingers.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(mid == hull.size() - 1) l = mid + 1;
            ~~~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(r >= 0 && r <= hull.size() - 1) ans = min(ans, Get(hull[r], x));
                  ~~^~~~~~~~~~~~~~~~~~
harbingers.cpp:55:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(l >= 0 && l <= hull.size() - 1) ans = min(ans, Get(hull[l], x));
                  ~~^~~~~~~~~~~~~~~~~~
harbingers.cpp: In function 'void DFS(long long int, long long int)':
harbingers.cpp:77:17: warning: unused variable 'cac' [-Wunused-variable]
             int cac = -1;
                 ^~~
harbingers.cpp: In function 'int32_t main()':
harbingers.cpp:96:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
harbingers.cpp:96:63: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]

• Subtask 1: 0 / 100